1 min read
| Status | Unfetched — filed 2026-10-15, not read. Registered at the owner's request as one of 22 works at the intersection of database theory and semantic search, as the predecessor of LIT-1115. A lawful full text exists for both versions but could not be fetched from this environment on 2026-10-15 ("found but could not be fetched"). The JCSS 1999 journal version (10.1006/jcss.1998.1600) is in Elsevier's open archive: Unpaywall, OpenAlex and Semantic Scholar all give sciencedirect.com/science/article/pii/S0022000098916002/pdf (bronze, publishedVersion), which returned 403, as did the article page and the download variant; linkinghub.elsevier.com resolves to that page, and the Elsevier API refused unauthenticated requests (429). The PODS 1996 extended abstract (10.1145/237661.237715) is open on the ACM Digital Library (Unpaywall and Semantic Scholar: gold), but dl.acm.org/doi/pdf/10.1145/237661.237715 returned 403. CORE lists a CiteSeerX-harvested copy (oai:citeseerx.psu:10.1.1.55.2172) whose abstract matches the journal paper; CiteSeerX reset the connection and redirected to web.archive.org, which is unreachable, and CORE does not serve its full text to the public API. OpenAlex also lists a CiteSeerX record 10.1.1.386.6808 (submittedVersion), likewise unreachable. IBM Research's publication page (research.ibm.com/publications/combining-fuzzy-information-from-multiple-systems) links only the DOI; guessed author paths on researcher.watson.ibm.com returned 404 and the old almaden.ibm.com host returned 503; CORE's download path returned 403. Web searches for the title with and without "pdf" found no author, institutional or course copy. Fagin, Lotem and Naor (LIT-1115, read) state this paper's main result as they report it: Fagin's Algorithm finds the top k with O(N^((m−1)/m) k^(1/m)) accesses with arbitrarily high probability when the lists' orderings are independent, and is optimal in that sense for strict combining functions. It stays Unfetched until it is read, not on merit; fetching the Elsevier open-archive PDF from a browser would settle it. |
| Version | 2 |
| Tags | databases, information-retrieval |
| Cited as “source” by | THEORY-379 — Fagin's Algorithm finds the top k of N objects held in m attribute-sorted lists under any monotone combining function, and when the lists' orderings are independent with at least m − 1 of them uniformly random it does so with O(N^((m−1)/m) k^(1/m)) sorted and random accesses with arbitrarily high probability; with dependent orderings the bound can fail, THEORY-832 — For strict combining functions and m attribute-sorted lists of N objects whose orderings are probabilistically independent, no correct top-k algorithm does essentially better than Fagin's Algorithm in the worst case with high probability: every one needs on the order of N^((m−1)/m) k^(1/m) accesses |
Fagin, R. (1996). Combining fuzzy information from multiple systems (extended abstract). In Proc. PODS 1996, pp. 216–226. DOI 10.1145/237661.237715. Journal version: Journal of Computer and System Sciences 58(1), 83–99 (1999), DOI 10.1006/jcss.1998.1600
Unfetched (see the status note).
The predecessor of LIT-1115, for CLAIM-310. Unfetched: open copies exist but none could be fetched.