k-RP*s: a scalable distributed data structure for high-performance multi-attribute access

k-RP*s is a new data structure for scalable multicomputer files with multi-attribute (k-d) keys. We discuss the k-RP*s file evolution and search algorithms. Performance analysis shows that a k-RP*s file can be much larger and orders of magnitude faster than a traditional k-d file. The speed-up is especially important for range and partial match searches that are often impractical with traditional k-d files. This opens up a new perspective for many applications