eBay Inc.
Data indexing and searching using permutation indexes

Abstract:

Systems and methods are provided for creating and utilizing search indexes with different properties to provide efficient and flexible means for retrieving and ranking high-dimensional content. A first index and a second index are generated with a different sets of properties, which may include a permutation prefix length and a vector quantization scheme, and are each associated with a computational workload. Further, at least one index structure may be created with a posting list associated with a permutation prefix and a set of references, rather than only a permutation prefix, to balance out posting lists of variable lengths within the index. Another embodiment of the disclosure provides for expansion of search results at search time, rather than during indexing, by retrieving posting lists associated with shorter permutation prefix after an initial list is determined to have insufficient recall.