High-Dimensional Indexing - Transformational Approaches to High-Dimensional Range and Similarity Searches

Sep 21, 2026

Uploaded by Anda

High-Dimensional Indexing presents transformational, indexing-centric methods for efficient query processing and knowledge discovery in high-dimensional databases. It addresses similarity search, range/window queries, K-nearest neighbor (KNN) queries, and similarity joins, showing why traditional multidimensional indexes such as R-trees scale poorly as dimensionality increases. The work proposes iMinMax(θ) for range/window query transformation with B+-tree indexing, and iDistance with metric-based partitions and reference/anchor points to enable efficient filtering and iterative KNN refinement while reducing costly distance computations.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages159

Reading Time6 h 41 min

AccessFree to download

Preface

Feature transformation and high-dimensional point search

Challenges with R-tree scalability in high dimensions

iMinMax(θ) for window/range queries

iDistance for similarity and KNN queries

Lecture Notes in Computer Science 2341 Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 3 Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Tokyo Cui Yu High-Dimensional Indexing Transformational Approaches to High-Dimensional Range and Similarity Searches 1 3 Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Author Cui Yu Monmouth University, Department of Computer Science West Long Branch, NJ 07764, USA National University of Singapore, Department of Computer Science Kent Ridge, Singapore 117543, Singapore [E-mail:cyu@monmouth.edu](E-mail:cyu@monmouth.edu) Cataloging-in-Publication Data applied for Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliograﬁe; detailed bibliographic data is available in the Internet at <[http://dnb.ddb.de](http://dnb.ddb.de)>. CR Subject Classiﬁcation (1998): H.3.1, H.2.8, H.3, H.2, E.2, E.1, H.4, H.5.1 ISSN 0302-9743 ISBN 3-540-44199-9 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, speciﬁcally the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microﬁlms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations areliable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH [http://www.springer.de](http://www.springer.de) © Springer-Verlag Berlin Heidelberg 2002 Printed in Germany Typesetting: Camera-ready by author, data conversion by Boller Mediendesign Printed on acid-free paper SPIN: 10869935 06/3142 5 4 3 2 1 0 Preface Many new applications, such as multimedia databases, employ the so-called feature transformation which transforms important features or properties of data objects into high-dimensional points. Searching for ‘similar’ objects based on these features is thus a search of points in this feature space. Another high-dimensional database example is stock price information systems, where time series data are stored and searched as high-dimensional data points. To support eﬃcient query processing and knowledge discovery in these highdimensional databases, high-dimensional indexes are required to prune the search space and eﬃcient similarity join strategies employing these indexes have to be designed. High-dimensional indexing has been considered an important means to facilitate fast query processing in data mining, fast retrieval, and similarity search in image and scientiﬁc databases. Existing multi-dimensional indexes such as R-trees are not scalable in terms of the number of dimensions. It has been observed that the performances of R-tree-based index structures deteriorate rapidly when the dimensionality of data is high [11, 12] . This is due to rapid growth in overlap in the directory with respect to growing dimensionality of data, requiring a large number of subtrees to be searched for each query. The problem is further exacerbated by the fact that a small high-dimensional query covering a very small fraction of the data space has actually a very large query width along each dimension. Larger query widthsimply that more subtrees need to be searched. In this monograph, we study the problem of high-dimensional indexing to support range, similarity, and K-nearest neighbor (KNN) queries, and similarity joins. To eﬃciently support window/range queries, we propose a simple and yet eﬃcient transformation-based method called the i

FAQs

What is iDistance designed to improve for similarity and KNN queries?

iDistance builds a metric-based index by partitioning the high-dimensional space and assigning each partition an anchor (reference) point. This enables transformed points to be indexed with a B+-tree and KNN search to be executed as a sequence of increasingly larger range queries, improving filtering and response time while reducing expensive distance calculations.

Sep 21, 2026

Uploaded by Anda