Searching on a Clustering Search Engine

The clustering of Web results is a novel Web searching technology that seems to offer some real benefits by structuring the deluge of information that Web searchers often face.

Clustering is the grouping together of similar search results. So, if the query is ‘apple’, all the results pertaining to fruit would be grouped together. All the results pertaining to the Apple technology company would be grouped together. Clustering has some interesting algorithmic challenges, including how to automatically name the groups!

In order to understand how Web searchers interact with clustering technology, I was involved in a research project that examined Web searchers using an operational clustering search engine, Vivisimo.

The search log contained 2,029,734 queries along with interactions with the results clusters.

The research results show the near typical Web searching interaction – short queries of about 2 terms, session lengths of about one query, and session durations of less than one minute.

A small percentage of users (about 2 percent) actually interacted with the clusters in terms of expanding the clusters. About half of user interactions with clusters consisted of displaying a cluster’s result set, and a small percentage of interactions showed cluster tree expansion.

Read the complete manuscript on Web searching and clustering of results

The Use of Simple Queries in Web Searching

The use of really simple queries by most Web users has been ridiculed by ‘more sophisticated’ folks as signs that most users of Web search engines are naïve about technology and searching.

Personally, I find this hard to believe as my basic premise is that ‘people are pretty smart’. So, why do folks use simple queries when Web searching?

The assumption of the ‘users are naïve’ crowd is that the use of query operators, such as Boolean operators and phrase searching, improves the effectiveness of Web searching.

I ran an experiment to test this assumption by examining the effects of query operators on the performance of three major Web search engines. We used one hundred queries from the transaction log of a Web search engine, so the queries represented real Web searching.

We took each of these queries without any operators and added operators such as AND, OR, MUST APPEAR (+), or PHRASE (“ ”). We submitted both the original and modified queries to three major Web search engines; a total of 600 queries were submitted and 5,748 documents evaluated.

We compared the results from the queries with the operators to the results from the queries without the operators. We examined the results for changes in coverage, precision, and ranking.

Findings? There was little to no different using query operators with coverage, precision, or ranking. Those Web searchers? Pretty smart.

Read the complete manuscript on the effect of various query structures on Web searching results

The Challenge of Doing Web Research in Academia Versus a Web Company

A challenge for academic researchers who conduct Web searching work is the issue of being relevant. At the crux of this issue is access to data, especially for folks doing empirical work.

The Web search engine companies, through the use of toolbars and search logs can easily access hundreds of thousands of interactions. Academics just don’t, generally, have access to user data on this magnitude. For algorithmic lines of research, the same issue holds – the collections used in academia are relative minor compared to what Web companies can access.

As a case in point, one year I attempted to publish (unsuccessfully) a paper on the use of implicit feedback to assist in determining the usefulness of search engine results. I had a user study of 42 participants. This same year, researchers from a major Web search engine company attempted to publish (and were successful) a manuscript on a similar topic. They had more than 100,000 users from logs of toolbar users.

To get that number of users for a study, I would need to recruit every student, faculty, and staff at Penn State, Texas A&M (two of the nation’s largest universities) plus the University of Virginia!

This really puts the pressure on academic Web researchers to be novel, pursue niche research in the area, or partner with Web searching companies.

Using the Web to Look for Work

One aspect of Web search is looking for work, either positions or consulting. The Web is now a significant component of the recruitment and job search process, with companies using the Web to recruit employees or locate needed expertise.

However, very little is known about how companies and job seekers use the Web, and the ultimate effectiveness of this process. I led a research study investigating how people search for jobs on the Web, how effective they are, and how likely they are to locate a job posting.

Using actual Web search engine queries, the research findings indicate that individuals seeking job information generally submit only one query with several terms and over 45 percent of job-seeking queries contain a specific location. Of the results, 52 percent are relevant and only 40 percent of job-specific searches retrieve job postings.

The findings point out that organizations using the Web to locate potential employees have a ways to go in effectively leveraging this venue.

Read the complete manuscript on using the Web for jobs and hiring

Information as Property

One of the theoretical issues in the information fields like Web searching, is ‘what is information’? The term ‘information’ is extremely overloaded, so it confuses communication.

There are cognitive definitions (i.e., information is part of a mental process), physical definitions (i.e., information physically exists, such as a document or Webpage), and contextual definitions (i.e., information as knowledge to address a situation).

One way address issue is to view the term ‘information’ as referring to a category. We have several such terms in the English language, property being one. In fact, one can draw an analogy between property and information.

Such an analogy helps delineate some of the multiple definitions that the field of information searching uses for information.

Like property, we must realize that information is not one simple thing, but is a great complex set of items, things, concepts, values and consequences.

Some of these ‘information-things’ (such as cognitive concepts, values) are virtual and personal, akin to labor – which is a property.

However, there are a great range of ‘information-things’ (e.g., published papers, conversations, images) that exist in the real world and created by some one, akin to real property.

Some of these tangible information things can be determined are how far and under what limitations they are private (i.e., private property). Others are very public, very particularly to determine, and how far it falls into the public domains (i.e., public property).

So, rather then just using ‘information’, someone needs to develop a list of qualifiers, like we do for property (e.g., real information, public information, virtual information, etc.)

Task Interrupts and Implicit Feedback

One issue with the use of implicit feedback in Web searching is the concern of task interrupts. When people are searching, they are focused on a task. System responses not directly related to this task are cognitive distractions.

The mental load of Web searching is high, notably in the situations where implicit feedback would be the most helpful. The interjection of some system response based on implicit feedback (i.e., contextual help or automated assistance) into the search process may be too much of a cognitive load, requiring a task switch from focusing on the search process to mentally processing the assistance. Therefore, searchers ignore or improperly implement the assistance.

I did some research investigating the issue of contextual help as task interrupts. Results from this research indicate that patterns of user-system interaction styles are short, typically only two or three interactions. Using a taxonomy of 26 interactions, the implicit feedback is categorized into nine groups. The majority of interactions are with result listings (approximately 20%) and selection of documents (approximately 15%). Interactions with system assistance are approximately 4%.

The key thing about interrupts is that searchers typically seek out assistance after interactions with the results listings, submitting the initial query, and browser navigation. So, these would be the best times for a system to interject contextual help into the searching process. Otherwise, the system should probably not interrupt the searcher.

Read the complete manuscript on temporal patterns, interrupts, and implicit feedback

Why Are You in the Business You’re In

I view being a professor at a land grant university as a service profession, similar to the military, clergy, law enforcement, etc. Part of being a professor is doing research. I do Web searching research.

I’ve fiddled around writing up my research goals (i.e., “improve the dissemination of information in our society”, "improve the way people locate and use information”, etc.) many times, trying to capture what I was really attempting to achieve. Have never been happy with it but was always on the look out for now to REALLY articulate what I was trying to do with my research.

Then two days ago, it happened.

My wife and I were at a wine dinner at a local restaurant. A vintner, (Alfrédo Bartholomeu), was speaking about his business approach. As part of his short and really good presentation, he said something that really got my attention, “I want to be in a business that makes us better people.”

And, that was it. That short sentence really captured the essence of what I would love to do with my research. Make us better people. Finding information more effectively and efficiently permits us to … make better health care decision, take better vacations, make better financial decisions, run our businesses better, make more informed politician decisions, find a long lost friend, etc. In other words, to become better people.

Implementing Implicit Feedback in Web Search Engines

Implicit feedback is an interesting and seemingly useful approach that one could use to improve the results of Web searching. There is certainly research using click through analysis (i.e., using the clicks on links in the results listing to provide indications of interest and relevance). Implicit feedback is seems useful in designing assistance and contextual help.

However, how can you actually implement it in search engine design? I have done research exploring the use of a software agent that uses implicit feedback to assists the user during the search process.

The agent was developed as a separate, stand-alone component to be integrated with existing information retrieval systems. I evaluated the contextual help component integrated with a search engine using 30 search engine users.

The research results indicate that implicit feedback can rapidly model user information needs, resulting in an improvement in precision (i.e., number of relevant results retrieved by the search engine).

The conceptual help features used were: Spelling (12%), Query refinement (56%), Terms from relevance feedback (3%), and Managing results (29%).

Read the complete manuscript on contextual help

Implicit Feedback Classifications and Patterns

In an earlier post on categories of implicit feedback, I presented some general classes of implicit feedback (i.e., user interactions with a search engines). However, these were really broad. For system design work, one needs something of finer granularity.

I ran a laboratory study to provide specific classifications of implicit feedback, with a focus on providing contextual help and automated assistance for Web searching. The study involved 40 participants. We identified 1,879 occurrences of searcher– system interactions patterns and classified them into 9 major categories and 27 subcategories or states.

We present a classification scheme of implicit feedback using system and content, with the Behavior Category as one axis and Scope (i.e., system or content) as the other. The Behavior Categories were Execute, Examine, Navigate, Retain, and Reference. The Scope categories were System and Content (i.e., segment of an object, object, or class of action).

The results indicate that there are predictable patterns or times when searchers desire and implement contextual help. The most common three-state pattern is Execute Query – View Results: With Scrolling – View Assistance.

Read the complete manuscript on implicit feedback classifications

Categories of Implicit Feedback

The use of interactions between searchers and search engines seems to hold the greatest potential for personalization of Web searching. The interactions used for personalization are called implicit feedback.

Implicit feedback holds a lot of potential and some promising results have already been obtained by a variety of researchers working in this area. The implicit feedback from searchers is combined with the query to provide a richer picture of what the user is looking for. A key aspect of leveraging implicit feedback is to provide contextual help or automated assistance, although there are other possible uses such as targeted ads.

A critical issue in designing contextual help systems is determining when the system should intervene in the search process. The first step is to identify the major categories of implicit feedback.

I did a research study analyzing the search process and when implicit feedback occurs. From an analysis of the study’s data, I identified seven categories of implicit feedback, which are: View Results Page, View Particular Document, View Offered Assistance, Execute Query, Implement Assistance, Navigation, and Action Indicating Relevance (such as print, save, bookmark, or copy). These seven categories account for 99.66% of all user interactions with the system.

Read the complete manuscript on categories of implicit feedback

Overlap Among Search Engine Results

Sponsored search is the most significant search innovation since page rank. Among the many other impacts, it provides a working business model to meta-search engines.

Meta-search is an interesting concept and seems like something that would be beneficial for the user. In a nutshell, a meta-search engine accepts a user query, submits this query to multiple other search engines, aggregates the results into a meaningful listing, and then services this to the user. Certainly seems beneficial to the user (results from many search engines, each of which individually can only index a portion of the Web).

Not so beneficial to the search engines that pay for the infrastructure to index the Web, store the results, fight spam, etc. Basically, these meta-search engines were just taking their customers with an infrastructure at a fraction of the cost. So, naturally, whenever these meta-search engines got too large, the other search engines would just block their IPs. Until sponsored search came along!

With sponsored search, these search engines return sponsored results along with the organic. Both the meta-search engine and the servicing search engine would split the revenue from the sponsored links. A workable business model for both! (Note: In practice, the search engines also charge these meta-search engines a fee to service their organic results.)

What about the searcher though? Interestingly, there has been little empirical work to see if the meta-search approach is really helping the user? I participated in a research study investigating the overlap among results retrieved by multiple Web search engines for a set of more than 10,000 queries. The research goal was to measure the overlap of search results on the first result page (both non-sponsored and sponsored) across the four most popular Web search engines (i.e., MSN Search, Google, Yahoo! and Ask Jeeves).

Findings show that nearly 85% of results were retrieved by only one of the four Web search engines! Only, about 1% of the results were retrieved by all four search engines. So, if one is looking for a range of results, meta-search does appear to provide this.

However, the overall value of meta-search depends on an environment were there are multiple search options. I am a big fan of Google, but it is healthy for everyone (even Google) if they have a couple of tough competitors out there.

Read the complete manuscript on comparing the overlap among Web search engine results

Comparison of Searching for Web, Image, Audio, and Video Content

The use of tabs for searching the various verticals (i.e., separate pages for audio, images, texts, video, and news) was a significant innovation by Web search engines when it was introduced. Prior to this, results all appeared together.

Now, perhaps not surprisingly, we are going back to different media results being integrated together, calling this retrofit universal search.

I have mixed views on the whole process, as searching for audio files versus images vs normal Web pages vs video has difference characteristics.

In a research study that I did, these tabs appeared to help users find information better than a universal search did.

Comparing general, audio, image, and video, image searching appears to be the more multifaceted task, and audio appears to be the least complex.

For example, our analysis showed that the mean terms per query for image searching was notably larger (4 terms) than the other categories of searching, which were less than 3 terms. The session lengths for image searching were longer than any other type of searching, although video sessions were also relatively lengthy. Boolean usage by image searchers was 28%, over four times the next highest ranked category of general Web searching.

For me, these findings points to separate searching episodes going on depending on the media being sought.

Read the complete manuscript on Web searching in multimedia verticals

We did a more recent study on searching audio, video, image, and news verticals

Publishing at Conferences versus in Journals

In many fields of research, but especially Web searching research where time to publish is critical, I have heard several times that journals take *so* long to publish an article while conferences are so quick.

Perhaps, this was true at one time, but it is not a hard and fast rule any more. With the use of online submission technology by journals, they are becoming *the medium* to get results out quickly … and journal articles are usually more in-depth than conference papers. So, the reader gets a fuller picture of the research.

Here is an example of the new timeline afforded by the use of submission technology for journal publishing.

First, the conference paper. Say the conference is in September. Then the conference submission is due typically in January. You submit the paper in January and are prohibited from submitting it anywhere else while under review. The reviews come back in April or May. Given the conference constraints of time and space, there is a good chance it will get rejected (i.e., rejection rates run about 80-85% for the decent conferences nowadays – primarily due to space and time restrictions). If it does get accepted, the final submission is typically due in June and the paper is made available sometime during the September conference. Total time to publish: approximately 7 months (230 days).

Now, the journal paper. You submit a journal paper in January. With the online submission systems and reviewer tracking that many journals now have, the review turn around is many times around 30 days or so. Assume that you get an ‘accept with minor revisions’ (similar to what a conference acceptance is) and get right on it, getting the paper back in two weeks. The journal editor and the publisher will mess around with it for about 4 to 6 weeks. At which time, it is now ready for publication in a hard copy issue at some point in the future. However, a lot of journals are now making press ready manuscripts IMMEDIATELY available online with a DOI --- and the journals that don’t will be doing it soon! So, the paper is available via download and citable some time around the end of March. Total time: approximately 3 months (90 days).

Total time savings: approximately 4 months by publishing a journal article instead of a conference paper!

So, a journal paper has a quicker publication time and, without the space and time constraints of conferences, has a better chance of getting accepted. Typcial rejection rates for decent journals are now around 70-75%. Plus since journal papers are usually longer, they can address a subject with more substance than can a conference paper, which is typically around 8 to 10 pages.

Certainly, conferences have their benefit, as social networking places, as good places for doctoral students’ symposiums, and being good to hear researchers present their work and respond to questions.

However, if you are looking for time to market, I believe journals are the better publication route in both time-to-publish and depth-of-material.

How to Conduct Search Log Analysis

Methods matter when one is conducting research, with various aspects of validity to be concerned with.

Methods also matter critically when comparing results across studies. The approach one takes, along with the terms that one uses, and how one defines these terms, can affect the interpretation of results by others and the accurate comparison of results..

I wrote a method piece concerning how to conduct search log analysis, which is the methodological approach used to analyze the data contained within search logs. The article presents a comprehensive review of prior literature and provides the foundation for conducting Web search log analysis, which is a sub-category of transaction log analysis.

The search log methodology is outlined in three stages, which are (1) collection, (2) preparation, and (3) analysis. I discuss the three stages of the methodology in detail, focusing on goals, metrics, and processes at each of the stages.

The article also defines critical terms in transaction log analysis and presents the strengths and limitations of transaction log analysis as a research method. The article also presents suggestions on ways to leverage the strengths of, while addressing the limitations of, transaction log analysis for Web-searching research.

Read the complete manuscript on how to conduct search log analysis

Software Agents Querying Web Search Engines

Usually, when we think of gathering information from Web search engines we picture a single person submitting a query or two.

However, there is a lot of automated querying of Web search engines. In these situations, a person uses a software program to submit the queries and, usually, scrap off the retrieved results. Situations where this occurs are folks writing their own script, search engine optimizers checking keywords, meta-search engines getting results from multiple search engines, and Web search engines who have opened their own API to other applications.

This automated searching is quite different than the Web search that we typically picture. How different?

In a research study that I participated in, we analyzed three data sets of search engine queries and page views from software agents interacting with the Web search engines. We examined approximately 900,000 queries submitted by more than 3,000 software agents.

Findings include:
(1) agent sessions are extremely interactive, with sometimes hundreds of interactions per second
(2) agent queries are comparable to human searchers, with little use of query operators,
(3) Web agents are searching for a relatively limited variety of information, wherein only 18% of the terms used are unique, and
(4) the duration of agent-Web search engine interaction typically spans several hours.

What is interesting about these findings is the load that they place on the network and the search engine. Since there is no economic advantage to be efficient (i.e., it is free to submit the queries and the network load is free), these programs aren’t efficient. They are extremely simple. It would seem that their should be some economic incentive applied to these software applications to improve performance.

Read the complete manuscript on software agents gathering information from Web search engines.

The Behaviors of Web Search Engine Users

It is always interesting, to me, to see how people are using Web search engines – the queries they use, the number of pages they view, the links they click, etc.

I find the whole gamut of Web searching just fascinating from a technical, social, cognitive, and commercial perspective with critical implications in each of these areas.

I recently did a study with some other researchers examining how people use search engines. We examined nearly 2.5 million interactions from more than 500K users of Dogpile. We also compared the results with findings from other Web searching studies

Findings show that Dogpile searchers use about 3 terms per query (mean of 2.85), implement system feedback moderately (8.4% of users) – Dogpile has a query assistance feature -- , and generally (56% of users) spend less than one minute interacting with the Web search engine.

Yes, that is correct, less than one minute. And, Dogpile ranks highly in user evaluations of satisfaction.

What was really interesting, again to me, was that the number of interactions was a *higher* than reported in other user studies but the *duration* of these set of interactions was *less*.

It may have something to do with these searchers using a meta-search engine (i.e., Dogpile) instead of a general purpose search engine like Google or Yahoo!

Read the complete manuscript concerning user actions while Web searching

Collaborative information behavior, seeking, and searching

An area that has some high pay off potential but has receive only minimal research attention is collaborative information searching (i.e., when two or more people collectively search for similar information to attend an shared need).

We do it all the time when working in groups, at work on collective problem, when doing planning, and even at home when looking at family vacations and such. However, there has been very little study into what triggers an episode of collaborative information seeking, what technologies are needed to support such activities, and how can one use technology to facilitate sharing of both information and the process to locate this information.

Some of the original work in collaborative information retrieval was done at the University of Washington. Microsoft is also doing work in collaborative information retrieval tools.

I’ve co-authored a paper on collaborative information searching, where my collaborator and I propose a framework composed of agents, users, information, and context.

I predict that we will see some commercial, niche search engines in this area soon.

It’s the Click not the Query

There is a lot of work focused on the query in Web searching. Certainly understandable for a lot of reasons.

However, the key element for the content providers and the search engine is the click? What do the users do AFTER the query? This is where the money is.

We know that about 40% of the time, users don’t click on ANY link on the search engine result page (SERP). This is reasonable from my own experiences, as many times I am looking for something that is answered on the SERP (e.g., the page numbers of an article, an authors name, the model of a product). ... Although, it would be great for the search engines if someone could find a way to dollarize these no-click searches.

I did some research examining how folks viewed SERP and the associated links off those pages. About 60% to 70% of users will never go beyond the first SERP. So, your Webpage has got to be there to have the best chance of being seen.

What about number of actual links clicked? Approximately 70% of users will only view 1 or 2 Webpages per query. So, competition is tight for the all important click. Over an entire session (i.e., a set of queries by a user), about half of the searchers will view no more than 3 pages.

I also looked at how long a user spends on the pages they viewed – about 14% of the users viewed a page for less than 30 seconds. So, you have to make that all important first impression.

Read the complete chapter on page viewing patterns of Web searchers

Searching for People on the Web

Most people have used a name as the query in a search engine, either searching for a potential date, one's significant other, a long lost friend, a famous person, or a vanity search (i.e., searching for one's own online presence).

I was interested in how prevalent this behavior was and how folks did. It has a lot of privacy implications (i.e., a good way to identify a Web search engine user is by the names they search on), societal implications (i.e., who do folks consider important or interesting), and commercial value (i.e., tying names of people to particular commercial Web sites). So, I conducted a research study to investigate.

My co-researcher and I found that queries with names were about 4% of queries, with celebrity searching being about 25% of this traffic. 4% is actually a good percentage of searches, BTW. Most of these queries were just the name with no quotes or any additional identify terms.

Read the compete research on searching for people on the Web

It would be really interesting to redo the research now, as the data was from pre-Facebook, LinkedIn, etc. And, would be interesting to see how much of this is vanity searching.

The implications are for businesses that manage the online perception of others, which seems like a good commercial niche.

Girls in the Science, Technology, Engineering, Mathematics Fields

As the father of three daughters, I am really interested in ensuring that my girls have the broadest range of career options available for them. I want them to have the opportunity to go into whatever field they are interested in and have the opportunity to go as far as their talents, efforts, and luck will take them.

There has been a great deal of concern at K12, undergraduate, and graduate levels concerning girls entering the Science, Technology, Engineering, Mathematics (STEM) areas. There has been a lot written about what possible causes and solutions concerning girls interested in the STEM fields.

One of my daughters recently attended a week-long summer camp, Girls and Mathematics, sponsored by two colleges of the University of Virginia (UVA). Forty middle-school girls doing a week of mathematics (hard stuff too!), with about half a dozen college-age instructors (all women). A UVA professor, Irina Mitrea, was the program organizer. While not perfect, the program was impressive. An ethnically diverse group, the kids were all normal looking and acting kids. The instructors all normal looking, and acting, college age women.

Although a multiple variable problem, my experiences as a father and a college professor point to overcoming stereotypes and peer pressure as one of the main issues of recruiting in these fields. There are these stereotypes ‘out there’ that if you are ‘good at math’, you look, dress, and act like a dork. And, conversely, if you look, dress, and act ‘normal’, then you can’t be good at math, or technology, or science, or engineering.

Some of the negative stereotypes have some basis, unfortunately. Funding agencies, especially, NSF have thrown money at this problem, usually focused on the student (as if they are the problem). Want to make an immediate impact? Get funding to have all the current STEM instructors – the men and the women -- to take a ‘what not to wear’ course.

Can’t tell you the number of professors doing research in this area that are re-enforcing the negative stereotypes. Or, the number of recruiting events or science camps that I have been too where the speaker or instructor looked and acted like they had just walked out of a Delbert cartoon.

That’s one thing I liked about the Girls and Mathematics camp – the whole thing ran by women. More importantly, though, good role models (i.e., no dorks), which is what’s needed to break some of these existing negative stereotypes.

Luckily, it appears that these stereotypes about girls and the STEM fields are breaking down already, as this article about ‘geek becomes chic’ discusses.

We need similar camps for girls in the tech area, although the search engine area has done pretty well in the demographic recruiting. When I visit the search engine or search engine marketing companies, there is a pretty gender diversity. I noticed the same thing in a search engine marketing course that I taught. I believe it has something to do with practical application of technology with the mix of business.

How Effective are E-shopping Search Engines?

Niche search engines (i.e., search engines focused on one domain) seem to be an effective way to improve searching performance. Conceptually, the idea makes a lot of sense. If you are searching for academic articles, you usually have better luck in a ‘research-only’ content collection.

However, does this work for all domains? I decided to test out the niche search engine concept for ecommerce.

I examined five different types of search engines in response to ecommerce queries by comparing the engine quality of ecommerce links using relevant ratings. This research used 100 ecommerce queries taken from a search engine log and verified with WordTracker as significant query topics. I examined five major search engines, each a different type (i.e., Meta-search, Ecommerce, General purpose, Pay per click and Directory). The five search engines used were: Excite (Meta search engine), Froogle (Ecommerce engine), Google (General engine), Overture (paid for inclusion engine), and Yahoo! Directory (Directory service engine). We examined more than 3,540 retrieved Web links, judging each for relevance to the query that retrieved it.

The findings? … Yup, an ecommerce search engine did better.

The results showed that links retrieved using an ecommerce search engine are significantly better than those obtained from most other engines types but do not significantly differ from links obtained from a Web directory service.

See the full paper comparing different types of Web search engines for ecommerce searching