dtunkelang

In general, the two ways to compute counts are top-down, by making a separate query for each filter, or bottom-up, by scanning the results and aggregating the counts, like a group-by. Top-down is good for a small universe of values, but bottom-up tends to be the scalable approach. And, as has been pointed out, you can produce approximations by aggregating a sample of the results -- as long as it is a representative random sample. Just be mindful of statistics, particularly confidence intervals.

A related issue is that counts tend to treat all results as equal. If you retrieva a lot of results but most of them are not relevant -- as can happen with full-text search -- then the counts can be misleading. You may have the converse problem if your retrieval excludes a lot of relevant results. So, if you are implementing a faceted search application where you use and show counts, you should keep in mind that it will only work if your retrieval does a reasonable job of balancing precision and recall.

Finally, remember that supply != demand. The distribution of a facet in your index may be different from the distribution of that facet in searcher intent. A bit more on that here: https://dtunkelang.medium.com/search-intent-not-inventory-28...

BTW, I highly recommend the Relevance Slack as a good space to discuss this and search-related topics generally. It's run by OpenSource Connections, but it's free and anyone can join, even folks who compete with them. It's the best community I have found for search developers.

https://opensourceconnections.com/blog/2021/07/06/building-t...

While the acquisition was good for me financially, I agree that Oracle didn't really invest in sustaining Endeca as a product. I am proud of what we achieved at Endeca, but search has come a long way since then.

Coincidentally, I now consult for Algolia. :-)

I've found that, for mobile screens, the most valuable refinement real estate is often the top row of the results. Since that space is very limited, there's only room for the most useful facets or filters. And you have to decide whether to show keys or values, e.g., "Brand" as a key or "Nike", "Adidas", etc. as values. Showing keys takes up less space and allows you to cover more ground, but showing values may be more useful -- and certainly more discoverable -- to the user, since there's one less step. As with all things, it's a tradeoff, and I don't think there's been that much research on optimizing it.

Thanks for the kind words! I'm not usually on HN, but I just discovered this thread and am happy to contribute if I have anything useful to add. The book is a bit dated, but I have continued to post about search more broadly on Medium, particularly on the topic of query understanding.

As others have pointed out, most search engines don't support natural language search in general, let alone natural language negation in particular.

There are several reasons for this, including the following:

1) Natural language understanding for search has gotten a lot better, but it is still not as robust as keyword matching. The upside of delighting some users with natural language understanding doesn't yet justify the downside of making the experience worse for everyone else.

2) Most users today don't use natural language search queries. That is surely a chicken-and-egg problem: perhaps users would love to use natural language search if it worked as well or better than keyword search. But that's where we are today. So, until there's a breakthrough, most search engine developers see more incremental gain from optimizing some form of keyword search than from trying to support natural language search.

3) Even if the search engine understands the search query perfectly, it still has to match that interpretation against the documentation representation. In general, it's a lot easier to understand a query like "shirt with stripes" than to reliably know which of the shirts in the catalog do or don't have stripes. No one has perfectly clean, complete, or consistent data. We need not just query understanding, but item understanding too.

4) Negation is especially hard. A search index tends to focus on including accurate content rather than exhaustive content. That makes it impossible to distinguish negation from not knowing. It's the classic problem of absence of evidence is not being evidence of absence. This is also a problem for keyword and boolean search -- negating a word generally won't negate synonyms or other variations of that word.

5) The people maintaining search indexes and searchers co-evolve to address -- or at least work around -- many of these issues. For example, most shoppers don't search for a "dress without sleeves"; they search for a "sleeveless dress". Everyone is motivated to drive towards a shared vocabulary, and that at least addresses the common cases.

None of this is to say that we shouldn't be striving to improve the way people and search engines communicate. But I'm not convinced that an example like this one sheds much light on the problem.

If you're curious to learn more about query understanding, I suggest you check out https://queryunderstanding.com/introduction-c98740502103

Yes, this is real. And she could really use the help. It was very brave of her to come forward this way: she took personal risk, and it's not like she's gaining anything from this personally. On the contrary, she's facing threats of legal action, as well as the risk that future employers might avoid her because of association with this dumpster fire.

"The idea was started because Daniel Tunkelang of Netflix was very anti RSS."

Um, what? I've never worked at Netflix, and I've never been anti-RSS. And I'm pretty sure there isn't another Daniel Tunkelang. :-)

Am curious to see having the dictionary in a trie allows you to build an implementation that is O(n). Will add it to the blog post if it works.

Peter actually emailed me directly, though I was already very familiar with his work on this and similar problems. But yes, I make it very clear in the post (and to candidates) that they should not assume an English -- or even a natural language -- dictionary.

Sorry. The post renders well in Chrome on my Mac and on my Nexus One. But apparently not so well in other browser / platform combinations.

I don't have stats I can share, but I assure you that this problem has confounded many interview candidates with strong resumes. I agree with you that it's all basic material -- that's deliberate. I'm glad you think it's too easy. :-)

Point taken. But it's hard to come up with good interview questions, as my colleagues here, at Google, and at Endeca can attest. In contrast, it's much easier to post solutions.

That's why I'm working on an approach that assumes the candidate does of prior knowledge of the problem. But not there yet.

Sorry about that. Advice on how to fix it while maintaining good rendering elsewhere? Looks good in Chrome on my MacBook and my Nexus One.

Secret is a strong word -- I link to another post on the subject in the article. Still, seeing it on Glassdoor for my own employer crossed the line of disclosure.

Point taken. I thought of not linking to them, or even not mentioning them. But they do play an important part in the story of the post, and I don't think I'm helping them so much as I'm raising employees' and employers' awareness of their existence. At least now a few more interviewers might check to see if their questions are posted there. From my limited data, interviewees are already more aware of Glassdoor than interviewers.

As for feeding them page rank, I don't think I have so much to offer that it helps them materially.

Actually, my original implementation used Dijkstra's algorithm. But I think the linear table of suffixes (or prefixes if you prefer) is a cleaner approach.

Exactly. I prefer legal reform too, but something is better than nothing.

Glad to see positive feedback about the PATO proposal. I can't claim credit for originality -- but I was glad that, when I thought of it independently, I was quickly able to discover John Walker's proposal.

I am glad to finally see this story told in all of its gory detail. As a witness to this story, I was frustrated to see how Arlo and AJ never had a chance to win on the merits of their case, let alone on the merits of their technology. I can only hope that this story inspires others and drive needed software patent reform. And that Arlo and AJ both go on to do great things -- as I am sure they are doing already.

Good to finally see this story told in all of its gory detail. As a witness to this story, I was frustrated to see how Arlo and AJ never had a chance to win on the merits of their case, let alone on the merits of their technology. I can only hope that this story inspires others and drives needed software patent reform. And that Arlo and AJ both go on to do great things -- as I am sure they are doing already.

Would love to hear feedback on the "practical" part of my rant. Unfortunately most of the comments on the post focused on the merits of software patents.

Let me be clear (as I am in the post): I don't like software patents. I think they should be eliminated. And yes, I realize the term "software patents" is vague, but we could work through that.

BUT...we're not going to eliminate software patents any time soon. My post is an attempt to offer practical advice to folks in the here and now.

Also look at Paul Haahr's letter: http://paulhaahr.com/blog/2010-09-26-my-letter-to-the-us-pat...

I'm obviously a big fan of LinkedIn, and I see them as a poster child for faceted search. I hope they take the next step and do interesting things with the skills data that is latent in their profiles. But I'm happy that they took the bold step of putting faceted search front and center--and that they're seeing great returns on that investment.

Also, my friend is reading this page, and I hope he'll reach out to folks who have volunteered to help. Bad patents hurt everyone--you never know if you'll be the next victim. Regardless of your stance on software patents in general, I hope you agree that that there are a lot of invalid software patents out there, and that their holders are wreaking havoc by what amounts to legalized extortion.

I'm asserting that it's a bad software patent because I'm familiar with the details. You obviously don't have to take it on faith that my assertion is correct. Believe me, I'd love to share the details--and I will when my friend gives me the go-ahead.

I agree with you that not all software patents are vague, overly broad, or anticipated by prior art. I've been on the other side myself.

Believe me, I'd love to give these guys bad press--TechCrunch or Gawker could do a nice story at their expense. But that's my friend's decision to make, not mine. The last thing I want to do is undermine his defense.

Thanks. I'm sensitive about parasitic blogging--in fact, I've blogged about it: http://thenoisychannel.com/2008/12/20/fair-use-and-seo/

In this instance, my genuine hope was to get people to read Jeremy's post, and an unsolicited email from Jeremy about his spike in traffic--which is how I found out that HN had picked up my post--assures me that I accomplished that.

I agree that people should read Jeremy Pickens's post at IR Gupf--that's why I wrote a "quick bite" on my blog which a teaser excerpt and a link. Evidently Jeremy is getting a lot of readers today (including Mark Johnson, the program manager of Bing), which makes me happy.

Sounds like we may have talked to the same guy. I agree that breadth of data is a challenge, and I didn't have the chance to push its limits. Though I was surprised that it knew about acids but not about the pH levels. That might be ok--and certainly fixable if it matters to enough people--but it's a reminder that there will always be holes.

It is interesting to imagine an approach like this raising the bar for information quality / provenance on the web. That would be a delightful outcome wrt information accountability.