論文 / 著書情報
Article / Book Information
Title

A File Search Method Based on Intertask Relationships Derived from
Access Frequency and RMC Operations on Files

AuthorYi Wu, Kenichi Otagiri, Yousuke Watanabe, Haruo Yokota

Journal/Book name

Lecture Notes in Computer Science, Vol. 2011, No. 6860/2011, pp.
364-378

発行日 / Issue date2011, 8

DOI

10.1007/978-3-642-23088-2̲27

権利情報 / Copyright

The original publication is available at www.springerlink.com.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

A File Search Method based on Intertask
Relationships Derived from Access Frequency
and RMC Operations on FilesYi Wu1?? , Kenichi Otagiri2 , Yousuke Watanabe3 , and Haruo Yokota1
1

Department of Computer Science, Tokyo Institute of Technology
2
Cowbell Engineering Corporation
3
Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology{goi,otagiri,watanabe}@de.cs.titech.ac.jp,yokota@cs.titech.ac.jp
http://yokota-www.cs.titech.ac.jp

Abstract. The tremendous growth in the number of ﬁles stored inﬁlesystems makes it increasingly diﬃcult to ﬁnd desired ﬁles. Traditional
keyword-based search engines are incapable of retrieving ﬁles that do notinclude keywords. To tackle this problem, we use ﬁle-access logs to derive intertask relationships for ﬁle search. Our observations are that 1)
ﬁles related to the same task are frequently used together, and 2) a setof Rename, Move, and Copy (RMC) operations tends to initiate a newtask. We have implemented a system named SUGOI, which detects two
types of task, FI tasks and RMC tasks, from ﬁle-access logs. An FI taskcorresponds to a group of ﬁles frequently accessed together. An RMC
task is generated by RMC operations and then constructs a graph ofintertask relationships based on the inﬂuence of RMC operations andthe similarity between tasks. In utilizing detected tasks and intertask
relationships, our system expands the search results of a keyword-based
search engine. Experiments using actual ﬁle-access logs indicate that the
proposed approach signiﬁcantly improves search results.
Keywords: ﬁle-access logs, desktop search, full-text search, task mining

1

Introduction

The explosion in the volume of information that people handle has been accompanied by daily increases in the number of ﬁles stored in ﬁlesystems. Many ofthese are unstructured ﬁles, such as images, diagrams, and numerical-data ﬁles,
which do not contain any appropriate text that can be used for search. As theseﬁles do not include the target keywords, traditional text-based desktop keyword
search engines are not useful for ﬁnding them.
A number of systems have been developed for desktop keyword search, such
as Google Desktop Search[3], Microsoft’s Windows Desktop Search[5], and Spotlight on Mac OS X[1]. These systems all develop indexes for high-speed search,??

The author is currently with NTT DATA Corporation.

2

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

and some use a thesaurus and meta-information such as the ﬁle name, creation
time, and ﬁle type, to improve search performance. However, it is still diﬃcult
to search for ﬁles that do not include text.
Recently, some desktop search systems, such as FRIDAL[9, 10] and Connections[8], have been proposed to tackle the problem of the association between
ﬁles based on the co-occurrence information derived from ﬁle-access logs. Thesesystems try to capture the relationships between ﬁles based on users’ access patterns. These approaches are eﬀective in searching for ﬁles that do not containtext. However, sometimes the searches return irrelevant ﬁles or fail to returnrelevant ﬁles because infrequent but important operations for ﬁles could not
be found and temporary simultaneous access of ﬁles inﬂuences the results fromthese approaches.
In this paper, to improve the accuracy of search results based on ﬁle-accesslogs, we focus on a task where a user accesses multiple ﬁles to accomplish his/hergoal. In other words, most ﬁles accumulated in a ﬁlesystem must be related toindividual tasks. We refer to a group of ﬁles that are used to accomplish aparticular goal as a “task.” Thus, in this paper, the term “task” represents alogical unit of ﬁles to be processed in a computer system, such as collating someexperimental data, writing a report or article, or preparing presentation slides.
Based on the concept of task, we propose a ﬁle search system named SUGOI—
Search by Utilizing Groups Of Interrelated ﬁles in a task—which consists of twoparts: a task mining component and a ﬁle search component. The task mining
component extracts tasks and discovers the interrelation between tasks fromﬁle-access logs. The ﬁle search component incorporates the task mining results
within the search results of a traditional desktop search engine to achieve an
accurate keyword-based ﬁle search.
We observed that 1) ﬁles related to the same task are frequently used together, and 2) a set of Rename, Move and Copy (RMC) operations tends toinitiate a new task. Therefore, the task mining component of SUGOI extracts
two types of task: FI (Frequent Itemset) tasks and RMC tasks. We then propose
formulas to combine FI and RMC tasks.
We also consider the graph of intertask relationships for retrieving related
ﬁles. Assuming that the greater the number of identical ﬁles accessed during
diﬀerent tasks, the stronger is the interrelation between these tasks, we build
similarity links between these tasks. In addition, we generate RMC links between
tasks, assuming that users tend to RMC ﬁles for reuse in related tasks. For
example, as researchers tend to use the same graph of experimental results inboth their articles and their presentation slides, they may copy the ﬁle of thegraph from the article folder to the presentation folder. In this case, the copy
operation indicates a strong relationship between the tasks of writing the article
and of preparing the presentation. To represent such intertask relationships, theweight of an RMC link is computed considering the type of the operation andits direction. We propose a formula to handle both types of links.
After the tasks and intertask relationships have been extracted, the ﬁle searchcomponent of SUGOI expands the search results of a traditional keyword-basedA File Search Method based on Intertask Relationships

3

search engine using the mined tasks and intertask relationships, and ranks thesearch results. We evaluate the proposed system using actual ﬁle-access logs. The
experimental results indicate that the proposed approach signiﬁcantly improves
recall and F-measure.
The remainder of this paper is organized as follows. Section 2 presents related
research on desktop search. Section 3 gives a detailed explanation of SUGOI
and Section 4 describes the experimental results and investigation. Section 5
concludes this paper and indicates future work.

2

Related Work

With the great increase in the capacity of storage devices, the volume of all
types of data is steadily increasing, with most being ﬁle-based and unstructured.
Users require more eﬀective and simpler mechanisms for managing vast numbers
of ﬁles, such as locating desired ﬁles easily from ﬁles scattered across diﬀerent
directories. Traditional content-based search tools cannot deal with ﬁles that do
not include the query keywords, and supported ﬁle formats are restricted. For
the purpose of enhancing full-text search, much research has been done usingﬁle-access logs. This section describes three previous studies that used ﬁle-accesslogs for ﬁle search.
As mentioned in Section 1, Connections [8] is a ﬁle search system that uses
contextual information with the aim of enhancing full-text search results. Connections generates a relational graph of ﬁles based on traces of ﬁlesystem calls.
To discover relationships, it splits access logs into multiple relation windows
and identiﬁes the input and output ﬁles in each window by considering which
operation is performed on the ﬁles. Connections then creates links with weight
1 from input ﬁles to output ﬁles or increases the weight of existing links. It
uses a Basic-BFS (Breadth First Search) algorithm to propagate the weights
of keyword-containing ﬁles to keyword-lacking ﬁles to expand and reorder the
results generated by a full-text search engine. By contrast, we utilize ﬁle-accesslogs to group ﬁles into tasks and identify the interrelations between tasks rather
than the relationships between ﬁles.
FRIDAL[9, 10] is another system for searching keyword-lacking ﬁles by using
the interﬁle relationship. FRIDAL exploits open/close logs in order to derive theduration for which the ﬁle is used. Assuming that ﬁles used at the same time
have some relevance to each other, FRIDAL calculates the interﬁle relationshipby using the co-occurrence data between ﬁles in access logs. It ﬁnds keywordlacking ﬁles by using a Basic-BFS-like method. By contrast, SUGOI emphasizes
tasks and only uses access patterns that occur frequently. Furthermore, we take
RMC operations into account in calculating the weight of semantic links between
tasks.
The iMecho[2] system performs task mining similar to SUGOI, building three
types of associations: Content-based Associations (CA), Explicit Activity-based
Associations (EAA), and Implicit Activity-based Associations (IAA). It reranks
the results of a full-text search engine, using a random walk algorithm based on

4

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

Fig. 1. Overview of SUGOIPageRank[7]. The purpose of the task mining in iMecho is to generate IAA links
between ﬁles; it does not consider the relationship between tasks. In addition,
the ranking score used in iMecho is deﬁned as the product of a full-text search
result and a link analysis result, so iMecho does not extend the result of a fulltext search to include non-text ﬁles. By contrast, SUGOI can extend the resultof a full-text search by task mining and detecting the relevance between tasks.

3

Proposed Approach

We propose an approach for searching ﬁles by introducing the concept of “tasks.”
Before the search process, we cluster related ﬁles as a task and discover the correlation between tasks by exploiting ﬁle-access logs. We then expand the resultsfrom a traditional keyword-search engine using the tasks and intertask relationships. We have implemented a prototype system using the proposed approachand named it “Search by Utilizing Groups Of Interrelated ﬁles in a task” or“SUGOI” for short. An overview of SUGOI is illustrated in Fig. 1. To trace user
access as ﬁle-access logs, SUGOI places an access monitor on the ﬁlesystem. The
ﬁle-access logs should include access time, information to identify the client, thepath of the target ﬁle, and the operation on it. After cleaning the log, the system extracts the semantic ﬁle groups as tasks, and builds weighted links between
tasks. Following a user’s search request, SUGOI searches for ﬁles by combining
the context of tasks with the traditional full-text search results to calculate thetask scores. The details of the proposed methods (apart from log cleaning) aredescribed in the following subsections. Log cleaning is described in Section 4.1,
because the process corresponds to the monitoring tool used in the experiments.
3.1

Task Mining

The purpose of task mining is to group those ﬁles that are related to the sametask. We extract two types of task: FI tasks and RMC tasks. After the task

A File Search Method based on Intertask Relationships

5

Fig. 2. Extraction of Transactions (TransactionTime = 3600 [s])Fig. 3. Extraction of an RMC Task (RMCTaskTime = 1800 [s])mining processes, a number of ﬁles accessed by a user belong to at least one
task.
FI Task Mining The FI task, or Frequent Itemset task, is constructed from ﬁlesaccessed concurrently. The point is that ﬁles related to the same task tend to beaccessed frequently within short time periods of each other. For example, whena user writes an article, he/she edits a TeX ﬁle as well as EPS ﬁles containing
charts and produces a PDF ﬁle. With this characteristic, we propose a method
to semantically group ﬁles as FI tasks by mining the access patterns that occur
frequently and simultaneously.
We ﬁrst convert the ﬁle-access logs into a set of transactions (Fig. 2) by splitting the logs into several transactions with a certain duration (T ransactionT ime).
To discover the frequent patterns, we apply an existing algorithm, Eclat[11], tothe set of transactions. Eclat is one of the best-known algorithms for mining
frequent itemsets. It ﬁnds combinations of items whose occurrence frequency
is greater than some minimum support value. In this study, we determine theminimum support count (M inSuppCnt) to extract frequent itemsets because
ﬁle-access logs last for a long period but common tasks last for a ﬁxed periodof time and the number of occurrences of each individual ﬁle should be small.
Finally, we extract the maximally frequent itemsets as FI tasks.

6

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

RMC Task Mining Assuming that the ﬁles RMCed together within a shorttime period are related to a task done in the past, we extract such ﬁle groups
as an RMC task. To mine RMC tasks, we split access logs into multiple time
windows with the same length of time and only extract the ﬁles that are thetarget of RMC operations (Fig. 3).
3.2

Intertask RelationshipThis subsection presents our proposed formulas for weighting the similarity links
and RMC links of tasks and calculating the relevance between tasks by considering the overlap and RMC operations between tasks. In addition, we consider
reducing the weight of RMC links because the content of ﬁles created by RMC
operations can diﬀer from the original by modiﬁcation.
Similarity Links Analysis Assuming that tasks that are strongly interrelated
use a number of common ﬁles, we weight the similarity links between tasks basedon the number of duplicated ﬁles in each task. The weight of a similarity linkfrom task i to task j, which is expressed as sim(ti → tj ), is given by Equation(1).
|ti ∩ tj |sim(ti → tj ) =
(1)
|ti |
Here, ti and tj represent the ﬁle sets of task i and task j, respectively.
RMC Links Analysis Supposing that a user RMCes ﬁles contained in related
task to reuse in other tasks, RMC operations can express a strong relationshipbetween tasks. We build RMC links of tasks by detecting an RMC operation
between diﬀerent tasks. To calculate the weight of RMC links, we introduce theelement rmcf (fm → fn ), which presents the weight from ﬁle m to ﬁle n causedby an RMC operation.

α1 if fm was renamed as fn ,
α2 if fm was renamed from fn ,
 β1 if fm was moved to fn ,rmcf (fm → fn ) = β2 if fm was moved from fn ,
(2)


γ
if
f
was
copied
to
f
,

1
m
n



γ2 if fm was copied from fn ,

0 otherwise.
According to Equation (2), we assign rmcf a constant value speciﬁed by theparameters (α1 , α2 , β1 , β2 , γ1 , γ2 ). However, the degree of relevance of eachﬁle will be attenuated because the content of ﬁles coming from RMC operations
probably diﬀers from that of the original ﬁles by repeated edits.
In addition to rmcf , we propose formulas to take into consideration thefactors that cause reduced relevance. Thus, we deﬁne the reduction formulas
using the elapsed time (Equation (3)), the sum of frequency of write operation

A File Search Method based on Intertask Relationships

7

handled to ﬁle fm and ﬁle fn (Equation (4)), and the sum of the sizes of thechanges to ﬁle fm and ﬁle fn after RMC operations performed (Equation (5)).
T (fm , fn ) = ∆time (fm , fn )−τ

(3)

E(fm , fn ) = ∆edit (fm , fn )−

(4)

S(fm , fn ) = ∆size (fm , fn )−σ(5)Here, τ , , σ are parameters. Considering the circumstances mentioned above, we
calculate the weight of an RMC link by using rmcf and the reduction functions(Equation (6)).
∑
rmc(ti → tj ) =rmcf (fm → fn ) ∗ T (fm , fn ) ∗ E(fm , fn ) ∗ S(fm , fn )(fm ,fn )∈(ti ,tj )(6)Intertask Relevance To calculate the degree of association between tasks,
we adopt the weight of similarity links and RMC links and use the parameterθ(0 ≤ θ ≤ 1) to control which element to emphasize. The proposed formula isgiven by Equation (7).
R(ti → tj ) = θ ∗ simt (ti → tj ) + (1 − θ) ∗ rmct (ti → tj )
3.3

(7)

Keyword-based File Search

In addition to ﬁles that include keywords, SUGOI can ﬁnd ﬁles contained in tasks
related to the keywords by combining the context and interrelation of tasks. This
subsection describes the procedure for keyword-based search.
STEP 1: Identify tasks containing the keyword-containing ﬁles. The initial relevance score of a task to the given keywords is assigned using the ﬁle score
given by the existing full-text search engine (Equation (8)).
∑
score0 (q, ti ) =scoref (q, fm )(8)
fm ∈tiHere, score0 (q, ti ) denotes the initial score of task ti to query q, andscoref (q, fm ) denotes the relevance score of ﬁle fm to the query. According toEquation (8), we use the summation of the ﬁle score to deﬁne the task score
so that the score of the tasks that do not contain the keyword-containing
ﬁles should be zero.
STEP 2: In this paper, we adopt a reﬂexive method based on Basic-BSF, which
is used in Connections[8] and FRIDAL[9, 10], to ﬁnd tasks that contain related ﬁles. To ﬁnd the ﬁles that do not contain keywords, we iterate thecalculation of the relevance score for all tasks K times for translating therelevance (score0 (q, ti )) to other tasks for emphaisizing tasks that linked with

8

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

many related tasks and giving score to tasks that do not contain keywordcontaining ﬁles. At the k-th (1 ≤ k ≤ K) calculation, the relevance score oftask ti is given by Equation (9).
∑scorek (q, ti ) = scorek−1 (q, ti ) +scorek−1 (q, tj ) ∗ R(tj → ti ) (9)tj ∈InLink(ti )Here, InLink(ti ) expresses the set of tasks whose links point to task ti .
STEP 3: Normalize the relevance score for all ti and output ﬁles contained intasks that satisfy scoreK (q, ti ) > T Hscore as results, where T Hscore is a
threshold parameter.

4

Experiments

4.1

Experimental Environment

To verify the eﬃciency of SUGOI, we conduct evaluation experiments by using
actual ﬁle-access logs gathered from a shared ﬁlesystem (Windows Server 2003
SP2, NTFS) used by our research group. To monitor the ﬁle access to the server,
we use a tool named FAccLog[6]. FAcclog records the logs by monitoring accessto the OS and the LAN adapter. Logging can be done almost in real time andincludes read, write, create, delete, and rename operations. The full path of thetarget ﬁle is also included, but in the case of a rename, the path is recorded as“path before rename  path after rename”. Since the raw logs have noise andsome necessary information is lacking, we apply the log-cleaning process before
the main mining process.
The logs created by machine access mostly generate an incorrect task mining
result, deriving groups of ﬁles with little reference to each other. Such kinds ofaccess often come from background processes such as virus scanning, extracting
indexes by a desktop search engine or making backups. In addition, in manycases, a lot of ﬁle access will occur in a short period. Therefore, we use two
thresholds (T Hmin and T Hsec ) to eliminate the background machine access fromlogs. If the number of accesses occurring in a one minute/second range is larger
than T Hmin /T Hsec , all of the log entries are ignored. We also prepare a ﬁlter
for detecting machine access by ﬁle extension.
The raw logs only distinguish rename operations; they do not move andcopy. To ﬁnd move operations, we treat entries whose directory part of the pathchanged after the rename as move operations. To detect copy operations, welook for a pattern of a create log entry occurring after a read log entry with thesame ﬁlename, and treat it as a copy operation.
The implementation of SUGOI uses an existing full-text search engine named
HyperEstraier[4]. In addition to plain text and HTML ﬁles, we can optionallysearch PDF, DOC, DOCX, XLS, XLSX, PPT, and PPTX.

A File Search Method based on Intertask Relationships

9

Table 1. Experimental Datasets

Dataset # log entries # ﬁles # ﬁles available for full-text search # relevant ﬁles
A
B
C
D
E
F
G

4.2

3591
2808
3424
5911
8203
5123
13102

201
416
318
764
642
3422
3258

137
113
276
311
335
1152
338

70
25
32
84
244
227
73

Experimental Setup

The purpose of the experiments was to verify the eﬀect of utilizing ﬁle-accesslogs for ﬁle search. We used datasets with keywords and lists of relevant ﬁlesprovided by seven testers. The system was evaluated by comparing the relevantﬁles except the ﬁles that were deleted from the ﬁlesystem. A summary of theexperimental datasets is given in Table 1. These datasets were gathered from
April to July 2010. There are more than 2 GB of raw data and the summary isof the logs after log cleaning.
The parameters below were ﬁxed during the experiments. In log cleaning,
T Hmin = 30, T Hsec = 5. To calculate the weight of RMC links, (τ, , σ) =(0, 0, 0). In keyword-based search, T Hscore = 0, K = 3.
4.3

Evaluation of Task Mining

To expand the full-text search results, we detect two types of tasks and derive the intertask relationships from ﬁle-access logs. As ﬁles contained in thesame task are identiﬁed with each other, the results of task mining should be
important. We ﬁrst set up these experiments to acquire appropriate values ofparameters used for task mining. The other parameters were ﬁxed as follows:(α1 , α2 , β1 , β2 , γ1 , γ2 ) = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0), θ = 0.5.
Parameter Tuning for FI Task Mining To determine the value ofT ransactionT ime and M inSuppCnt, we only used FI tasks, and experiments
were performed in the combinations of T ransactionT ime = {900, 1800, 3600,
5400, 7200} [s] and M inSuppCnt = {2, 3}.
The averages of the F-measure are depicted in Fig. 4. The M inSuppCnt =2 case performed better than the M inSuppCnt = 3 case, with the value ofT ransactionT ime held constant. Increasing M inSuppCnt caused the number
of ﬁles belonging to tasks to decrease; this indicates that related ﬁles that do
not include keywords cannot be found by either tasks or intertask relationships. In addition, we notice a trend of the F-measure decreasing when the10

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota
Table 2. Average F-measure (FI Task Mining)

TransactionTime [s]MinSuppCnt=2
MinSuppCnt=3

900 1800 3600 5400 7200
0.543 0.513 0.507 0.470 0.506
0.452 0.432 0.450 0.411 0.453

Fig. 4. Experimental Results for FI Task Mining

T ransactionT ime increases. This is because, as T ransactionT ime increases,
more related ﬁles are put into the same transaction, and the number of ﬁles in aset of transactions will be less than M inSuppCnt because the number of accesses
is only counted once during the T ransactionT ime-long interval. We omit thedetails of the experimental results for each dataset because of space limitations.
Analysis of the results indicates that T ransactionT ime = 3600 accomplishedthe highest F-measure on datasets A, B and E, while T ransactionT ime = 900
showed the best performance on datasets C, D, F and G. Diﬀerences in work
patterns can be inferred from these results. Based on the results, we used a
diﬀerent T ransactionT ime in subsequent experiments.
Parameter Tuning for RMC Task Mining RM CT askT ime is the parameter used in extracting RMC tasks. To determine the value, in addition to
FI tasks, we use the RMC tasks extracted in each case of RM CT askT ime ={60, 180, 300, 600, 1800} [s] to perform ﬁle search.
As shown in Table 3, the average recall increased as RM CT askT ime increased. However, the average precision decreased slightly, because a long
RM CT askT ime potentially brings unrelated ﬁles into the same RMC tasks.
As the RMC operations were not handled very frequently, the impact was
small and caused little change in the F-measure. In subsequent experiments,
RM CT askT ime was set to 60 s.
4.4

Evaluation of Intertask Relationships

Relationships between tasks are derived from similarity links and RMC links.
In this section, we conduct experiments to determine the appropriate values ofA File Search Method based on Intertask Relationships

11

Table 3. Average F-measure (RMC Task Mining)

RMCTaskTime [s]Precision
RecallF-measure

60

180

300

600 1800

0.776 0.758 0.762 0.762 0.756
0.669 0.674 0.673 0.675 0.684
0.684 0.681 0.679 0.684 0.684

Table 4. Setups for Comparison of RMC Operations

Setup

Rename Move Copy
α1 α2 β1 β2 γ1 γ2

non-RMC
Rename
Move
Copy
RMC

0
1
0
0
1

0
1
0
0
1

0
0
1
0
1

0
0
1
0
1

0
0
0
1
1

0
0
0
1
1

parameters used in the formulas deﬁned for calculating the weights of links andthe degree of intertask relevance.
Experiments for RMC Links RMC links, an aspect used for determining
intertask relevance, are weighted using Equation (6), which considers the typeand direction between ﬁles, by introducing rmcf . rmcf is deﬁned by Equation(2) and the six parameters (α1 , α2 , β1 , β2 , γ1 , γ2 ). To compare RMC operations,
we set these parameters according to the conﬁguration given in Table 4. As theresults depicted in Fig. 5 show, using the rename and move operations had little
eﬀect on expanding the results of traditional ﬁle search. One reason is that renamed and moved ﬁles were ignored because ﬁles that do not exist in the ﬁlesystem were outside the evaluation targets. Another reason is that only 2% of log
entries are created from rename and move operations. In contrast with rename
and move, the copy operation enhanced the value of recall and the F-measureof full-text search results. Hence the result which utilized RMC performed thebest F-measure, we set (α1 , α2 , β1 , β2 , γ1 , γ2 ) = (1.0, 1.0, 1.0, 1.0, 1.0, 1.0) in subsequent experiments.
Experiment with θ In Equation (7), we use θ to adjust the relative emphasis on similarity links and RMC links when calculating the degree of intertask
relevance. To investigate the proper value of θ, we average the 11-point average
precision with θ = {0.0, 0.2, 0.4, 0.6, 0.8, 1.0}.
As shown in Fig. 6, better-ranking results were obtained when θ > 0.0 thanwhen θ = 0.0, although the precise value of θ was not so important. Because

12

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

Fig. 5. Comparison of Experimental Results on RMC Links

Fig. 6. Experimental Results for θ

tasks that have more links to other tasks tend to obtain a higher score under the
proposed method, even if the degree of intertask relevance changes, tasks of thisnature would be prioritized. θ = 0.0 led to a poor performance because using
RMC links only was not suﬃcient to expand the full-text results to other tasks.
We also note that θ = {0.2, 0.4} got the highest 11-point average precisions(Table 5).
4.5

Evaluation of SUGOITo improve the results of an existing keyword-based search engine, we group ﬁlesrelated to the same tasks and derive intertask relationships from access frequency
and RMC operations on ﬁles. We propose methods for mining FI tasks and RMC
tasks. To expand the full-text search results, we use similarity links and RMC
links to determine the relevance between tasks. To investigate the eﬀect of task
mining and the association links, we use the setup shown in Table 6 to compare
SUGOI with an existing full-text search engine[4].
The experimental results are given in Table 7 and Fig.7. All conﬁgurationsof the proposed system SUGOI are better according to the F-measure thanthe existing full-text search engine. FI tasks and similarity links increased theaverage of recall from 0.273 to 0.5, while precision increased from 0.795 to 0.820

A File Search Method based on Intertask Relationships

13

Table 5. 11-point Average Precision

θ
0.0
0.2
0.4 0.6 0.8 1.0
Average of 11-point Average Precision 0.430 0.482 0.482 0.476 0.476 0.475

Table 6. Setup of SUGOI

Setup

Task TypeIntertask Relational Links

SUGOI 1FI Task Only
Similarity Links Only
SUGOI 2FI Task Only Similarity Links + RMC Links
Similarity Links Only
SUGOI 3 FI Task + RMC Task
SUGOI 4 FI Task + RMC Task Similarity Links + RMC Links(SUGOI 1). In general, there is a trade-oﬀ between precision and recall. However,FI tasks consist of groups of ﬁles that are frequently accessed together and theaverage size of FI tasks is small, so few nonrelevant ﬁles are mingled in FI tasks.
In comparing SUGOI 1 with SUGOI 2 and SUGOI 3 with SUGOI 4, without
RMC tasks, the eﬀect of RMC links was small. An analysis of the mining results
showed that only about 9% of log entries were RMC entries and most RMCed
ﬁles were not contained in FI tasks because of low access frequency. Therefore,
it was diﬃcult to ﬁnd new FI tasks using RMC links.
In addition to FI tasks and similarity, using RMC tasks and RMC links
resulted in a certain improvement in recall and F-measure (SUGOI 3, 4). The
reason is that ﬁles that do not include the keywords were found because they
are related to tasks with ﬁles that do include the keywords. Thus, the precision
average decreased slightly because RMC tasks are extracted from ﬁles RMCed
together and, in contrast with FI tasks, extraneous ﬁles are easily mingled in
RMC tasks.
From Table. 7, it is clear that SUGOI 4 achieved the highest recall and Fmeasure. The result conﬁrmed that our proposed methods for task mining andderiving the intertask relationships are signiﬁcantly eﬀective for ﬁle search.
4.6

Summary of Experiments

In this section, we inspected the characteristics of the parameters and conﬁrmed
the validity of SUGOI by using actual ﬁle-access logs. The following conclusions
were obtained.
1. A lower minimal support count (M inSuppCnt = 2) generated results witha higher F-measure. This means that if a combination of ﬁle accesses occurs
more than twice in a set of transactions, these ﬁles are likely to have relevanceto each other.

14

Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota

Fig. 7. Experimental Results of SUGOI
Table 7. Experimental Results of SUGOI

Setup

Precision Recall F-measure

Traditional Full-text Search
SUGOI 1SUGOI 2SUGOI 3SUGOI 4

0.795
0.820
0.820
0.784
0.776

0.273
0.500
0.500
0.638
0.669

0.392
0.606
0.606
0.668
0.684

2. In the experiment on RMC task mining, we observed the trend that increasing RM CT askT ime decreases the precision and increases the recall.
However, the eﬀect is small because users do not perform RMC operations
frequently.
3. Copy operations, which can be done without making changes to the original
ﬁle, were the most eﬀective in RMC.
4. By investigating θ, a parameter used in Equation (7), we found that emphasizing the RMC links is eﬀective, but the similarity links were also essential.
SUGOI generated the best-ranking results when θ = {0.2, 0.4}.
5. SUGOI conspicuously improves the average recall and F-measure over traditional full-text search results. The recall rise represented an increase of
0.396, while the increase in the F-measure was 0.292.

5

Conclusion and Future WorkAs the volume of data stored in ﬁlesystems is increasing rapidly, and a large
proportion of this is ﬁle-based unstructured data such as multimedia ﬁles, manyﬁles cannot be found using traditional full-text search engines. In this paper, we
proposed a method for searching for such ﬁles by introducing the concept of tasks
and intertask relationships derived from ﬁle-access logs. The main contributionsof this paper are summarized as follows.

A File Search Method based on Intertask Relationships

15

1. Task mining methods for two types of task: FI tasks, consisting of ﬁles frequently accessed together, and RMC tasks, consisting of ﬁles that were renamed/moved/copied (RMCed) simultaneously.
2. Methods for deriving association links from ﬁle-access logs by considering
the similarity and RMC operations between tasks to generate a graph ofintertask relationships.
3. A search method incorporating the task mining results into a full-text searchto accomplish an accurate keyword-based ﬁle search.
4. Experimental results using actual ﬁle-access logs, which demonstrated thatthe proposed approach signiﬁcantly improves search results.
As future work, we plan to conduct evaluation experiments using larger ﬁleaccess logs. Contriving measures to choose the parameters automatically is also
important for practical use. We also want to reﬁne the proposed methods of task
mining and the formulas for indicating intertask relevance.

Acknowledgments
This research was supported in part by a MEXT Grant-in-Aid for ScientiﬁcResearch on Priority Areas (#201013017) and a JSPS Grant-in-Aid for ScientiﬁcResearch (A) (#22240005).

References
1. Apple Inc.: Spotlight,
http://www.apple.com/macosx/what-is-macosx/spotlight.html
2. Chen, J., Guo, H., Wu, W., Wang, W.: iMecho: an associative memory based
desktop search system. In: CIKM ’09: Proceeding of the 18th ACM conference on
Information and knowledge management. pp. 731–740. ACM, New York, NY, USA(2009)
3. Google: Google Desktop, http://desktop.google.com
4. Hirabayashi, M.: Hyper Estraier, http://fallabs.com/hyperestraier/
5. Microsoft Corporation: Windows Search,
http://www.microsoft.com/windows/products/winfamily/desktopsearch/
6. Daikoku Net: FAccLog, http://www2s.biglobe.ne.jp/˜masa-nak/fal down.htm
7. Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking:
Bringing Order to the Web. Tech. rep., Stanford University (1998)
8. Soules, C.A.N., Ganger, G.R.: Connections: using context to enhance ﬁle search.
SIGOPS Oper. Syst. Rev. 39(5), 119–132 (2005)
9. Watanabe, T., Kobayashi, T., Yokota, H.: A Method for Searching KeywordLacking Files Based on Interﬁle Relationships. In: OTM ’08. pp. 14–15. SpringerVerlag, Berlin, Heidelberg (2008)
10. Watanabe, T., Kobayashi, T., Yokota, H.: Searching Keyword-lacking Files Basedon Latent Interﬁle relationship. In: Software and Data Technologies. pp. 236–244(2010)
11. Zaki, M.J., Parthasarathy, S., Ogihara, M., Li, W.: New Algorithms for Fast Discovery of Association Rules. In: KDD-97 Proceedings. pp. 283–286 (1997)