NDLI: The pyramid-technique:towards breaking the curse of dimensionality

Content Provider	ACM Digital Library
Author	Kriegal, Hans-Peter Berchtold, Stefan Böhm, Christian
Abstract	In this paper, we propose the Pyramid-Technique, a new indexing method for high-dimensional data spaces. The Pyramid-Technique is highly adapted to range query processing using the maximum metric Lmax. In contrast to all other index structures, the performance of the Pyramid-Technique does not deteriorate when processing range queries on data of higher dimensionality. The Pyramid-Technique is based on a special partitioning strategy which is optimized for high-dimensional data. The basic idea is to divide the data space first into 2d pyramids sharing the center point of the space as a top. In a second step, the single pyramids are cut into slices parallel to the basis of the pyramid. These slices from the data pages. Furthermore, we show that this partition provides a mapping from the given d-dimensional space to a 1-dimensional space. Therefore, we are able to use a B+-tree to manage the transformed data. As an analytical evaluation of our technique for hypercube range queries and uniform data distribution shows, the Pyramid-Technique clearly outperforms index structures using other partitioning strategies. To demonstrate the practical relevance of our technique, we experimentally compared the Pyramid-Technique with the X-tree, the Hilbert R-tree, and the Linear Scan. The results of our experiments using both, synthetic and real data, demonstrate that the Pyramid-Technique outperforms the X-tree and the Hilbert R-tree by a factor of up to 14 (number of page accesses) and up to 2500 (total elapsed time) for range queries.
Starting Page	142
Ending Page	153
Page Count	12
File Format	PDF
ISSN	01635808
DOI	10.1145/276305.276318
Journal	ACM SIGMOD Record (SGMD)
Volume Number	27
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-06-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The pyramid-technique: towards breaking the curse of dimensionality

Database systems—breaking out of the box

Indexing medium-dimensionality data in Oracle

Class separation through variance: a new application of outlier detection

Towards Breaking the Curse of Dimensionality for High-Dimensional

Dimensionality reduction for similarity searching in dynamic databases

Hubness-aware shared neighbor distances for high-dimensional $$k$$ -nearest neighbor classification

Locally adaptive dimensionality reduction for indexing large time series databases

On Breaking The Curse of Dimensionality in Reverse Engineering Feature Models

The pyramid-technique:towards breaking the curse of dimensionality

Similar Documents

The pyramid-technique: towards breaking the curse of dimensionality

Database systems—breaking out of the box

Indexing medium-dimensionality data in Oracle

Class separation through variance: a new application of outlier detection

Towards Breaking the Curse of Dimensionality for High-Dimensional

Dimensionality reduction for similarity searching in dynamic databases

Hubness-aware shared neighbor distances for high-dimensional $$k$$ -nearest neighbor classification

Locally adaptive dimensionality reduction for indexing large time series databases

On Breaking The Curse of Dimensionality in Reverse Engineering Feature Models

The pyramid-technique:towards breaking the curse of dimensionality