View in EDS

Near neighbor searching with K nearest references.

Saved in:
Bibliographic Details
Title: Near neighbor searching with K nearest references.
Authors: Chávez, E.1 elchavez@cicese.mx, Graff, M.2 mario.graff@infotec.com.mx, Navarro, G.3 gnavarro@dcc.uchile.cl, Téllez, E.S.2 eric.tellez@infotec.com.mx
Source: Information Systems. Jul2015, Vol. 51, p43-61. 19p.
Subjects: Search algorithms, Databases, Data structures, Approximation theory, Mathematical models
Abstract: Proximity searching is the problem of retrieving, from a given database, those objects closest to a query. To avoid exhaustive searching, data structures called indexes are built on the database prior to serving queries. The curse of dimensionality is a well-known problem for indexes: in spaces with sufficiently concentrated distance histograms, no index outperforms an exhaustive scan of the database. In recent years, a number of indexes for approximate proximity searching have been proposed. These are able to cope with the curse of dimensionality in exchange for returning an answer that might be slightly different from the correct one. In this paper we show that many of those recent indexes can be understood as variants of a simple general model based on K-nearest reference signatures. A set of references is chosen from the database, and the signature of each object consists of the K references nearest to the object. At query time, the signature of the query is computed and the search examines only the objects whose signature is close enough to that of the query. Many known and novel indexes are obtained by considering different ways to determine how much detail the signature records (e.g., just the set of nearest references, or also their proximity order to the object, or also their distances to the object, and so on), how the similarity between signatures is defined, and how the parameters are tuned. In addition, we introduce a space-efficient representation for those families of indexes, making it possible to search very large databases in main memory. Small indexes are cache friendly, inducing faster queries. We perform exhaustive experiments comparing several known and new indexes that derive from our framework, evaluating their time performance, memory usage, and quality of approximation. The best indexes outperform the state of the art, offering an attractive balance between all these aspects, and turn out to be excellent choices in many scenarios. Our framework gives high flexibility to design new indexes. [ABSTRACT FROM AUTHOR]
Copyright of Information Systems is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 102000989
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Near neighbor searching with K nearest references.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Chávez%2C+E%2E%22">Chávez, E.</searchLink><relatesTo>1</relatesTo><i> elchavez@cicese.mx</i><br /><searchLink fieldCode="AR" term="%22Graff%2C+M%2E%22">Graff, M.</searchLink><relatesTo>2</relatesTo><i> mario.graff@infotec.com.mx</i><br /><searchLink fieldCode="AR" term="%22Navarro%2C+G%2E%22">Navarro, G.</searchLink><relatesTo>3</relatesTo><i> gnavarro@dcc.uchile.cl</i><br /><searchLink fieldCode="AR" term="%22Téllez%2C+E%2ES%2E%22">Téllez, E.S.</searchLink><relatesTo>2</relatesTo><i> eric.tellez@infotec.com.mx</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+Systems%22">Information Systems</searchLink>. Jul2015, Vol. 51, p43-61. 19p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Search+algorithms%22">Search algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Databases%22">Databases</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+models%22">Mathematical models</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Proximity searching is the problem of retrieving, from a given database, those objects closest to a query. To avoid exhaustive searching, data structures called indexes are built on the database prior to serving queries. The curse of dimensionality is a well-known problem for indexes: in spaces with sufficiently concentrated distance histograms, no index outperforms an exhaustive scan of the database. In recent years, a number of indexes for approximate proximity searching have been proposed. These are able to cope with the curse of dimensionality in exchange for returning an answer that might be slightly different from the correct one. In this paper we show that many of those recent indexes can be understood as variants of a simple general model based on K-nearest reference signatures. A set of references is chosen from the database, and the signature of each object consists of the K references nearest to the object. At query time, the signature of the query is computed and the search examines only the objects whose signature is close enough to that of the query. Many known and novel indexes are obtained by considering different ways to determine how much detail the signature records (e.g., just the set of nearest references, or also their proximity order to the object, or also their distances to the object, and so on), how the similarity between signatures is defined, and how the parameters are tuned. In addition, we introduce a space-efficient representation for those families of indexes, making it possible to search very large databases in main memory. Small indexes are cache friendly, inducing faster queries. We perform exhaustive experiments comparing several known and new indexes that derive from our framework, evaluating their time performance, memory usage, and quality of approximation. The best indexes outperform the state of the art, offering an attractive balance between all these aspects, and turn out to be excellent choices in many scenarios. Our framework gives high flexibility to design new indexes. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information Systems is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=102000989
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.is.2015.02.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 19
        StartPage: 43
    Subjects:
      – SubjectFull: Search algorithms
        Type: general
      – SubjectFull: Databases
        Type: general
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: Approximation theory
        Type: general
      – SubjectFull: Mathematical models
        Type: general
    Titles:
      – TitleFull: Near neighbor searching with K nearest references.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Chávez, E.
      – PersonEntity:
          Name:
            NameFull: Graff, M.
      – PersonEntity:
          Name:
            NameFull: Navarro, G.
      – PersonEntity:
          Name:
            NameFull: Téllez, E.S.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 07
              Text: Jul2015
              Type: published
              Y: 2015
          Identifiers:
            – Type: issn-print
              Value: 03064379
          Numbering:
            – Type: volume
              Value: 51
          Titles:
            – TitleFull: Information Systems
              Type: main
ResultId 1