Revision: 14560
http://gate.svn.sourceforge.net/gate/?rev=14560&view=rev
Author: valyt
Date: 2011-11-17 10:07:57 +0000 (Thu, 17 Nov 2011)
Log Message:
-----------
Possible solution for doing ranked and non-ranked query running sharing the
same code.
Modified Paths:
--------------
mimir/trunk/mimir-core/src/gate/mimir/search/QueryEngine.java
mimir/trunk/mimir-core/src/gate/mimir/search/RankingQueryRunnerImpl.java
Modified: mimir/trunk/mimir-core/src/gate/mimir/search/QueryEngine.java
===================================================================
--- mimir/trunk/mimir-core/src/gate/mimir/search/QueryEngine.java
2011-11-17 02:18:02 UTC (rev 14559)
+++ mimir/trunk/mimir-core/src/gate/mimir/search/QueryEngine.java
2011-11-17 10:07:57 UTC (rev 14560)
@@ -173,9 +173,9 @@
protected Executor executor;
/**
- * How many documents get ranked in the first instance.
+ * How many documents get ranked in one ranking stage.
*/
- private int rankedDocumentsCount = 1000;
+ private int rankingDocCount = 1000;
/**
* A list of currently active QueryRunners. This is used to close all active
@@ -213,16 +213,22 @@
/**
* Gets the configuration parameter specifying the number of documents that
- * get ranked in the first instance. This is used to optimise the search
- * process by limiting the nuber of results that get calculated by default.
+ * get ranked in one ranking stage. This is used to optimise the search
+ * process by limiting the number of results that get calculated by default.
* @return
*/
- public int getRankedDocumentsCount() {
- return rankedDocumentsCount;
+ public int getRankingDocCount() {
+ return rankingDocCount;
}
- public void setRankedDocumentsCount(int rankedDocumentsCount) {
- this.rankedDocumentsCount = rankedDocumentsCount;
+ /**
+ * Sets the configuration parameter specifying the number of documents that
+ * get ranked in one ranking stage. This is used to optimise the search
+ * process by limiting the number of results that get calculated by default.
+ * @param rankingDocCount
+ */
+ public void setRankingDocCount(int rankingDocCount) {
+ this.rankingDocCount = rankingDocCount;
}
/**
Modified:
mimir/trunk/mimir-core/src/gate/mimir/search/RankingQueryRunnerImpl.java
===================================================================
--- mimir/trunk/mimir-core/src/gate/mimir/search/RankingQueryRunnerImpl.java
2011-11-17 02:18:02 UTC (rev 14559)
+++ mimir/trunk/mimir-core/src/gate/mimir/search/RankingQueryRunnerImpl.java
2011-11-17 10:07:57 UTC (rev 14560)
@@ -24,8 +24,11 @@
import it.unimi.dsi.fastutil.doubles.DoubleArrayList;
import it.unimi.dsi.fastutil.doubles.DoubleList;
import it.unimi.dsi.fastutil.ints.Int2IntFunction;
+import it.unimi.dsi.fastutil.ints.IntAVLTreeSet;
import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntIterator;
import it.unimi.dsi.fastutil.ints.IntList;
+import it.unimi.dsi.fastutil.ints.IntSortedSet;
import it.unimi.dsi.fastutil.objects.ObjectArrayList;
import it.unimi.dsi.fastutil.objects.ObjectList;
@@ -42,20 +45,90 @@
*/
public class RankingQueryRunnerImpl implements QueryRunner, Runnable {
+ /**
+ * When doing ranking, this class is used to delegate the iteration of
+ * document IDs to an IntIterator that is limited to a finite set of
documents
+ * that have just been ranked. When that iterator is emptied, the
+ * {@link RankingQueryRunnerImpl#documentsById} field is nullified before
+ * hasNext() returns false, to indicate that more documents may be available.
+ */
+ protected class RankedDocIdIterator implements IntIterator {
+
+ public RankedDocIdIterator(IntIterator underlyingIterator) {
+ this.underlyingIterator = underlyingIterator;
+ }
+
+ protected IntIterator underlyingIterator;
+
+ public boolean hasNext() {
+ return underlyingIterator.hasNext();
+ }
+
+ public Integer next() {
+ return underlyingIterator.next();
+ }
+
+ public void remove() {
+ underlyingIterator.remove();
+ }
+
+ public int nextInt() {
+ return underlyingIterator.nextInt();
+ }
+
+ public int skip(int n) {
+ return underlyingIterator.skip(n);
+ }
+
+ }
+
protected Logger logger = Logger.getLogger(RankingQueryRunnerImpl.class);
+ /**
+ * The {@link QueryExecutor} for the query being run.
+ */
protected QueryExecutor queryExecutor;
+ /**
+ * The {@link MimirScorer} to be used for ranking documents.
+ */
protected MimirScorer scorer;
+ /**
+ * The document IDs for the documents found to contain hits. This list is
+ * sorted in ascending documentID order.
+ */
protected IntList documentIds;
+ /**
+ * If scoring is enabled ({@link #scorer} is not <code>null</code>), this
list
+ * contains the scores for the documents found to contain hits. This list is
+ * aligned to {@link #documentIds}.
+ */
protected DoubleList documentScores;
+ /**
+ * The sets of hits for each returned document. This data structure is
lazily
+ * built, so some elements may be null.
+ */
protected ObjectList<Binding[]> documentHits;
- protected IntList documentsByRank;
+ /**
+ * The order the documents should be returned in (elements in this list are
+ * indexes in {@link #documentIds}).
+ */
+ protected IntList documentsOrder;
+ /**
+ * An iterator supplying documentIDs in ascending order. These are used when
+ * collecting the hits.
+ */
+ protected IntIterator documentsById;
+
+ /**
+ * The thread used for executing the query. This is a separate thread from
one
+ * that created the query runner.
+ */
protected Thread runningThread;
/**
@@ -68,6 +141,7 @@
public RankingQueryRunnerImpl(QueryExecutor executor, MimirScorer scorer)
throws IOException {
this.queryExecutor = executor;
this.scorer = scorer;
+ documentsById = null;
// start the search
getMoreHits();
}
@@ -246,6 +320,103 @@
// TODO Auto-generated method stub
}
+
+ /**
+ * Creates an {@link IntIterator} used for enumerating the documents in the
+ * correct order for returning to the user.
+ * If no more documents are available, this should return null
+ * @return
+ * @throws IOException
+ */
+ protected IntIterator getDocumentIterator() throws IOException {
+ if(scorer != null) {
+ // we're doing ranking
+ if(documentIds == null) {
+ // first stage: collect all documents and their scores
+ documentIds = new IntArrayList();
+ documentScores = new DoubleArrayList();
+ documentHits = new ObjectArrayList<Binding[]>();
+ documentsOrder = new IntArrayList(
+ queryExecutor.getQueryEngine().getRankingDocCount());
+
+ scorer.wrap(queryExecutor);
+ int docId = scorer.nextDocument(-1);
+ while(docId >= 0) {
+ documentIds.add(docId);
+ documentScores.add(scorer.score());
+ documentHits.add(null);
+ docId = scorer.nextDocument(-1);
+ }
+ }
+ // collect some more ranked documents
+
+ int rankRangeStart = documentsOrder.size();
+ int rankRangeEnd = documentsOrder.size() +
+ queryExecutor.getQueryEngine().getRankingDocCount();
+ int docsByRankWriteIndex = rankRangeStart;
+
+ // the document with the minimum score already ranked.
+ int smallestOldScoreDocId = rankRangeStart > 0 ?
+ documentIds.getInt(documentsOrder.getInt(rankRangeStart -1))
+ : -1;
+ // the score for the document above, which is a the upper limit for new
scores
+ double smallestOldScore = rankRangeStart > 0 ?
+ documentScores.getDouble(documentsOrder.getInt(rankRangeStart -1))
+ : -1;
+ // the documentIds for newly ranked documents
+ IntSortedSet newDocuments = new IntAVLTreeSet();
+ // now collect some more documents
+ for(int i = 0; i < documentIds.size(); i++) {
+ int documentId = documentIds.getInt(i);
+ double documentScore = documentScores.getDouble(i);
+ // the index for the document with the smallest score,
+ // from the new ones being ranked
+ int smallestDocIndex = rankRangeStart < documentsOrder.size() ?
+ documentsOrder.getInt(rankRangeStart) : -1;
+ // the smallest score that's been seen in this new round
+ double smallestNewScore = smallestDocIndex == -1 ? 0.0 :
+ documentScores.getDouble(smallestDocIndex);
+ // we care about this new document if:
+ // - we haven't collected enough documents yet, or
+ // - it has a better score than the smallest score so far, but a
+ // smaller score than the maximum permitted score (i.e. it has not
+ // already been ranked)., or
+ // - it's a new document with the same score as the largest permitted
score
+ if(docsByRankWriteIndex < rankRangeEnd
+ ||
+ (documentScore > smallestNewScore &&
+ (smallestOldScore < 0 || documentScore < smallestOldScore))
+ ||
+ documentScore == smallestOldScore && documentId !=
smallestOldScoreDocId) {
+ if(docsByRankWriteIndex == rankRangeEnd) {
+ // we need to remove the newly ranked document
+ // with the smallest score
+ docsByRankWriteIndex--;
+ int oldDocIndex = documentsOrder.removeInt(docsByRankWriteIndex);
+ newDocuments.remove(documentIds.getInt(oldDocIndex));
+ }
+ // find the rank for the new doc
+ int rank = rankRangeStart;
+ while(rank < documentsOrder.size() &&
+ documentScore <
documentScores.getDouble(documentsOrder.getInt(rank))){
+ rank++;
+ }
+ documentsOrder.add(rank, i);
+ newDocuments.add(documentId);
+ docsByRankWriteIndex++;
+ }
+ }
+ if(newDocuments.isEmpty()){
+ return null;
+ } else {
+ return new RankedDocIdIterator(newDocuments.iterator());
+ }
+ } else {
+ // we're not doing scoring, simply use the queryExecutor as an
intIterator
+ return queryExecutor;
+ }
+ }
+
public void run() {
//store the running thread
synchronized(this) {
@@ -256,85 +427,12 @@
runningThread = Thread.currentThread();
}
try {
- if(scorer != null) {
- // we're doing ranking
- if(documentIds == null) {
- // first stage: collect all documents and their scores
- documentIds = new IntArrayList();
- documentScores = new DoubleArrayList();
- documentHits = new ObjectArrayList<Binding[]>();
- documentsByRank = new IntArrayList(
- queryExecutor.getQueryEngine().getRankedDocumentsCount());
-
- scorer.wrap(queryExecutor);
- int docId = scorer.nextDocument(-1);
- while(docId >= 0) {
- documentIds.add(docId);
- documentScores.add(scorer.score());
- docId = scorer.nextDocument(-1);
- }
- }
- // collect some more ranked documents
- int rankRangeStart = documentsByRank.size();
- int rankRangeEnd = documentsByRank.size() +
- queryExecutor.getQueryEngine().getRankedDocumentsCount();
- int docsByRankWriteIndex = rankRangeStart;
+ if(documentsById == null) {
+ documentsById = getDocumentIterator();
+ }
+ // collect the hits
+ while(documentsById != null) {
- // the document with the minimum score already ranked.
- int smallestOldScoreDocId = rankRangeStart > 0 ?
- documentIds.getInt(documentsByRank.getInt(rankRangeStart -1))
- : -1;
- // the score for the document above, which is a the upper limit for
new scores
- double smallestOldScore = rankRangeStart > 0 ?
- documentScores.getDouble(documentsByRank.getInt(rankRangeStart -1))
- : -1;
- for(int i = 0; i < documentIds.size(); i++) {
- int documentId = documentIds.getInt(i);
- double documentScore = documentScores.getDouble(i);
- // XxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXx
- // !!! Note that the documentsByRank is sorted in DESCENDING order
now
-
- // the index for the document with the smallest score,
- // from the new ones being ranked
- int smallestDocIndex = rankRangeStart < documentsByRank.size() ?
- documentsByRank.getInt(rankRangeStart) : -1;
- // the smallest score that's been seen in this new round
- double smallestNewScore = smallestDocIndex == -1 ? 0.0 :
- documentScores.getDouble(smallestDocIndex);
- // we care about this new document if:
- // - we haven't collected enough documents yet, or
- // - it has a better score than the smallest score so far, but a
- // smaller score than the maximum permitted score (i.e. it has not
- // already been ranked)., or
- // - it's a new document with the same score as the largest
permitted score
- if(docsByRankWriteIndex < rankRangeEnd
- ||
- (documentScore > smallestNewScore &&
- (smallestOldScore < 0 || documentScore < smallestOldScore))
- ||
- documentScore == smallestOldScore && documentId !=
smallestOldScoreDocId) {
- if(docsByRankWriteIndex == rankRangeEnd) {
- // we need to remove the newly ranked document
- // with the smallest score
- docsByRankWriteIndex--;
- documentsByRank.removeInt(docsByRankWriteIndex);
- }
-
- // find the rank for the new doc
- int rank = rankRangeStart;
- while(rank < documentsByRank.size() &&
- documentScore <
documentScores.getDouble(documentsByRank.getInt(rank))){
- rank++;
- }
- documentsByRank.add(rank, i);
- docsByRankWriteIndex++;
- // XxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXx
- }
- // collect the hits for the newly ranked docs
- }
-
- } else {
- // TODO: non-ranking mode implementation
}
} catch(IOException e) {
//something went bad!
This was sent by the SourceForge.net collaborative development platform, the
world's largest Open Source development site.
------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure
contains a definitive record of customers, application performance,
security threats, fraudulent activity, and more. Splunk takes this
data and makes sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-novd2d
_______________________________________________
GATE-cvs mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gate-cvs
