NDLI: Effective and Efficient Algorithms for Flexible Aggregate Similarity Search in High Dimensional Spaces

Content Provider	IEEE Xplore Digital Library
Author	Houle, M.E. Xiguo Ma Oria, V.
Copyright Year	1989
Abstract	Numerous applications in different fields, such as spatial databases, multimedia databases, data mining, and recommender systems, may benefit from efficient and effective aggregate similarity search, also known as aggregate nearest neighbor (AggNN) search. Given a group of query objects Q, the goal of AggNN is to retrieve the k most similar objects from the database, where the underlying similarity measure is defined as an aggregation (usually sum or max) of the distances between the retrieved objects and every query object in Q. Recently, the problem was generalized so as to retrieve the k objects which are most similar to a fixed proportion of the elements of Q. This variant of aggregate similarity search is referred to as “flexible AggNN”, or FANN. In this work, we propose two approximation algorithms, one for the sum variant of FANN, and the other for the max variant. Extensive experiments are provided showing that, relative to state-of-the-art approaches (both exact and approximate), our algorithms produce query results with good accuracy, while at the same time being very efficient.
Sponsorship	IEEE IEEE Comput. Soc. Tech. Committee on Data Eng IEEE Computer Society
Starting Page	3258
Ending Page	3273
Page Count	16
File Size	1346008
File Format	PDF
ISSN	10414347
Volume Number	27
Issue Number	12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-12-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Spatial databases Approximation methods Approximation algorithms Multimedia databases Data mining Recommender systems dimensional test Similarity search aggregation intrinsic dimensionality
Content Type	Text
Resource Type	Article
Subject	Information Systems Computational Theory and Mathematics Computer Science Applications

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

Dimensionality reduction and similarity computation by inner-product approximations

Efficient Correlation Search from Graph Databases

Scalable Probabilistic Similarity Ranking in Uncertain Databases

Multiple similarity queries: a basic DBMS operation for mining in metric databases

CSVD: clustering and singular value decomposition for approximate similarity search in high-dimensional spaces

Efficient Similarity Search in Nonmetric Spaces with Local Constant Embedding

Bounded Approximation: A New Criterion for Dimensionality Reduction Approximation in Similarity Search

Practical Algorithms and Lower Bounds for Similarity Search in Massive Graphs

High dimensional similarity joins: algorithms and performance evaluation

Effective and Efficient Algorithms for Flexible Aggregate Similarity Search in High Dimensional Spaces

Similar Documents

Dimensionality reduction and similarity computation by inner-product approximations

Efficient Correlation Search from Graph Databases

Scalable Probabilistic Similarity Ranking in Uncertain Databases

Multiple similarity queries: a basic DBMS operation for mining in metric databases

CSVD: clustering and singular value decomposition for approximate similarity search in high-dimensional spaces

Efficient Similarity Search in Nonmetric Spaces with Local Constant Embedding

Bounded Approximation: A New Criterion for Dimensionality Reduction Approximation in Similarity Search

Practical Algorithms and Lower Bounds for Similarity Search in Massive Graphs

High dimensional similarity joins: algorithms and performance evaluation

Effective and Efficient Algorithms for Flexible Aggregate Similarity Search in High Dimensional Spaces