检索结果-内蒙古大学图书馆

On the average performance of orthogonal range search in multidimensional data structures

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC 2002年第1期44卷 226-245页

作者： Duch, A Martínez, C Univ Politecn Cataluna Dept Lienguatges Sist Informat E-08034 Barcelona Spain LANIA Xalapa Veracruz Mexico

In this work we present the average-case analysis of orthogonal range search for several multidimensional data structures. We first consider random relaxed K-d trees as a prototypical example. Later we extend these results to many different multidimensional data structures. We show that the performance of range searches is related to the performance of a variant of partial matches using a mixture of geometric and combinatorial arguments. This reduction simplifies the analysis and allows us to give exact upper and lower bounds for the performance of range searches (Theorems 3 and 4) and a useful characterization of the cost of range search as a sum of the costs of partial match-like operations (Theorem 5). Using these results, we can act very precise asymptotic estimates for the expected cost of range searches (Theorem 6). (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： orthogonal range search multidimensional data structures multidimensional search partial match search K-d trees quadtrees average-case analysis

来源：评论

学校读者我要写书评

暂无评论

On Attribute-Based Encryption for Access Control to multidimensional data structures 1st

On Attribute-Based Encryption for Access Control to Multidim...

引用

1st International Early Research Career Enhancement School on Biologically Inspired Cognitive Architectures and Cybersecurity (FIERCES)

作者： Epishkina, Anna Zapechnikov, Sergey Natl Res Nucl Univ MEPhI Moscow Engn Phys Inst Moscow Russia

ISBN: (纸本)9783319639406;9783319639390

multidimensional data structures are widely used in modern information technologies. They sometimes contain private or other sensitive information. We argue that attribute-based encryption is a handy tool for access control to multidimensional data structures, discussing the advantages and disadvantages of ciphertext-policy and key-policy attribute-based encryption for this task. We propose a scheme of attribute management for multidimensional data structures.

关键词： multidimensional data structures OLAP Access control Attribute-based encryption

来源：评论

学校读者我要写书评

暂无评论

DYNAMIC QUANTIZATION - 2 ADAPTIVE data-structures FOR multidimensional SPACES

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1984年第3期6卷 266-280页

作者： OROURKE, J SLOAN, KR MIT ARCHITECTURE MACHINE GRPCAMBRIDGEMA 02139

Two new data structures are defined for use in multidimensional histogramming. Their purpose is to cover a parameter space with a limited number of histogram bins so that fine precision is maintained where it is needed. The original motivation for these data structures was to implement Hough-like transforms in high-dimensional parameter spaces. The two data structures share the ability to adapt to distributions that change with time.","doi":"10.1109/TPAMI.1984.4767519","publicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","startPage":"266","endPage":"280","rightsLink":"http://***/AppDispatchServlet?publisherName=ieee&publication=0162-8828&title=Dynamic+Quantization%3A+Two+Adaptive+data+structures+for+multidimensional+Spaces&isbn=&publicationDate=May+1984&author=Joseph+O%27Rourke&ContentID=10.1109/TPAMI.1984.4767519&orderBeanReset=true&startPage=266&endPage=280&volumeNum=PAMI-6&issueNum=3","displayPublicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","pdfPath":"/iel5/34/4767514/***","keywords":[{"type":"IEEE Keywords","kwd":["Quantization","data structures","multidimensional systems","Histograms","Voting","Tree data structures","Extraterrestrial measurements","Space technology","Computer architecture","Pixel"]},{"type":"Author Keywords ","kwd":["pyramids","Accumulator arrays","dynamic data structures","dynamic quantization","hierarchical data structures","Hough transform","k-d trees","multidimensional data structures","multidimensional histograms"]}],"allowComments":false,"pubLink":"/xpl/***?punumber=34","issueLink":"/xpl/***?isnumber=4767514","standardTitle":"Dynamic Quantization: Two Adaptive data structures for multidimensional Spaces

关键词： Quantization data structures multidimensional systems Histograms Voting Tree data structures Extraterrestrial measurements Space technology Computer architecture Pixel Author Keywords pyramids Accumulator arrays dynamic data structures dynamic quantization hierarchical data structures Hough transform k-d trees multidimensional data structures multidimensional histograms

来源：评论

学校读者我要写书评

暂无评论

Techniques and data structures for efficient multimedia retrieval based on similarity

引用

IEEE TRANSACTIONS ON MULTIMEDIA 2002年第3期4卷 372-384页

作者： Lu, GJ Monash Univ Grad Sch Comp & Informat Technol Churchill Vic 3842 Australia

As more and more information is captured and stored in the digital form, many techniques and systems have been developed for indexing and retrieval of text documents, audio, images, and video. The retrieval is normally based on similarities between extracted feature vectors of the query and stored items. Feature vectors are usually multidimensional. When the number of stored objects and/or the number of dimensions of the feature vectors are large, it will be too slow to linearly search all stored feature vectors to find those that satisfy the query criteria. Techniques and data structures are thus required to organize feature vectors and manage the search process so that objects relevant to the query can be located quickly. This paper provides a survey of these techniques and data structures.

关键词： efficient search multidimensional data structures multimedia databases multimedia indexing and retrieval

来源：评论

学校读者我要写书评

暂无评论

Efficient data structures for Online QoS-Constrained data Transfer Scheduling

Efficient Data Structures for Online QoS-Constrained Data Tr...

引用

7th International Symposium on Parallel and Distributed Computing

作者： Andreica, Mugurel Ionut Tapus, Nicolae Univ Politehn Bucuresti Dept Comp Sci Bucharest Romania

ISBN: (纸本)9780769534725

Distributed applications and services requiring the transfer of large amounts (if data have been developed and deployed till around the world. The best effort behavior of the Internet cannot offer to these applications the necessary Quality of Service (QoS) guarantees, making the development of data transfer scheduling techniques a necessity. In this paper we propose novel methods of efficiently using some wellknown data structures (e.g. the segment tree and the block partition), which can be implemented in a resource manager (e.g. Grid job scheduler, bandwidth broker) in order to serve quickly large numbers of advance resource reservation and allocation requests.

关键词： data transfer scheduling block partitioning segment tree multidimensional data structures algorithmic framework range query range update

来源：评论

学校读者我要写书评

暂无评论

THE QUADTREE AND RELATED HIERARCHICAL data-structures

引用

COMPUTING SURVEYS 1984年第2期16卷 187-260页

作者： SAMET, H Computer Science Department University of Maryland College Park Maryland

A tutorial survey is presented of the quadtree and related hierarchical data structures. They are based on the principle of recursive decomposition. The emphasis is on the representation of data used in applications in image processing, computer graphics, geographic information systems, and robotics. There is a greater emphasis on region data (i.e., two-dimensional shapes) and to a lesser extent on point, curvilinear, and three-dimensional data. A number of operations in which such data structures find use are examined in greater detail. [ABSTRACT FROM AUTHOR]

关键词： Geographic information systems hierarchical data structures image databases multiattribute data multidimensional data structures octrees pattern recognition point data quadtrees robotics.

来源：评论

学校读者我要写书评

暂无评论

A BALANCED HIERARCHICAL data STRUCTURE FOR multidimensional data WITH HIGHLY EFFICIENT DYNAMIC CHARACTERISTICS

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 1993年第4期5卷 682-694页

作者： NAKAMURA, Y ABE, S OHSAWA, Y SAKAUCHI, M SAITAMA UNIV FAC ENGNURAWASAITAMA 338JAPAN UNIV TOKYO INST IND SCIMINATO KUTOKYO 106JAPAN

A new multidimensional data structure, multidimensional tree (MD-tree), is proposed. The MD-tree is developed by extending the concept of the B-tree to the multidimensional data, so that the MD-tree is a height balanced tree similar to the B-tree. The theoretical worst-case storage utilization is guaranteed to hold more than 66.7%(2/3) of full capacity. In this paper, the structure of the MD-tree and the algorithms to perform the insertion, deletion, and spatial searching am described. By the series of simulation tests, the performances of the MD-tree and conventional methods are compared. The results indicate that storage utilization is more than 80% in practice, and that retrieval performance and dynamic characteristics are superior to conventional methods.

关键词： B-TREE BINARY TREE HEIGHT BALANCED TREES HIERARCHICAL data structures GEOGRAPHIC INFORMATION SYSTEM multidimensional data structures RANGE QUERIES SPATIAL data structures TREE structures 2-3 TREE

来源：评论

学校读者我要写书评

暂无评论

ALGORITHMS FOR BD TREES

引用

SOFTWARE-PRACTICE & EXPERIENCE 1986年第12期16卷 1077-1096页

作者： DANDAMUDI, SP SORENSON, PG Department of Computational Science University of Saskatchewan Saskatoon Saskatchewan S7N 0WO Canada

database applications often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most are generalizations of the storage structures used for managing one-dimensional data. Recently, a new storage structure, called the BD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. This paper presents algorithms for the BD tree to perform insertion, deletion, and to answer exact match, partial match and range queries. In addition, some experimental evidence is presented that suggests that BD trees have good dynamic characteristics.

关键词： multidimensional data structures File structures databases Multikey searching Partial match query Range query

来源：评论

学校读者我要写书评

暂无评论

multidimensional HEIGHT-BALANCED TREES

引用

IEEE TRANSACTIONS ON COMPUTERS 1984年第4期33卷 334-343页

作者： VAISHNAVI, VK Department of Information Systems Georgia State University Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions

A new multidimensional balanced tree structure is presented for the efficient management of multidimensional data. It is shown that the data structure can be used to manage a set of n k-dimensional records or data items such that the records can be searched or updated in O(log2 n) + k time, which is optimal. The data structure is a multidimensional generalization of the height-balanced trees and retains much of their simplicity and efficiency. The insertion algorithm, in particular, retains a very important property of the height-balanced trees: an insertion of a record results in the application of a restructuring operation at most once.

关键词： Computational geometry dynamic databases height-balanced trees information storage and retrieval multidimensional algorithms multidimensional balanced tree structures multidimensional data structures

来源：评论

学校读者我要写书评

暂无评论

Efficient skycube computation using point and domain-based filtering

引用

INFORMATION SCIENCES 2010年第7期180卷 1090-1103页

作者： Kailasam, Gayathri Tambaram Lee, Jin-Seung Rhee, Jae-Won Kang, Jaewoo Korea Univ Seoul South Korea Microsoft Corp Redmond WA 98052 USA

Skyline queries have been increasingly used in multi-criteria decision making and data mining applications. They retrieve a set of interesting points from a potentially large set of data points. A point is said to be interesting if it is not dominated by any other point. Skyline cube (skycube) consists of skylines of all possible non-empty subsets of a given set of dimensions. In this paper, we propose two algorithms for computing skycube using bitmaps that are derivable from indexes. The Point-based skycube algorithm is an improvement over the existing Bitmap algorithm, extended to compute skycube. The Point-based algorithm processes one point at a time to check for skylines in all subspaces. The Domain-based skycube algorithm views points as value combinations and probes entire search space for potential skyline points. It significantly reduces bitmap access for low cardinality, dimensions. Our experimental study shows that the two algorithms strictly dominate, or at least comparable to, the current skycube algorithm in most of the cases, suggesting that such an approach could be a useful addition to the set of skyline query processing techniques. (C) 2009 Elsevier Inc. All rights reserved.

关键词： database Skycube Skyline Algorithm Index multidimensional data structures Multi-criteria decision making

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：