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

Relationship Extraction Methods Based on Co-occurrence in Web
Pages and Files

Author

Qiang Song, Yousuke Watanabe, Haruo Yokota

Citation(English)

Proceeding of The 13th International Conference on Information
Integration and Web-based Applications & Services, , , pp. 82 - 89

Issue date2011, 12

Copyright

Copyright (c) 2011 Association for Computing Machinery

Note

This is the definitive version
http://www.iiwas.org/conferences/iiwas2011/,
http://dx.doi.org/10.1145/2095536.2095552

Set statement(c) ACM, 2011. This is the author's version of the work. It is posted
here by permission of ACM for your personal use. Not for redistribution.
The definitive version was published in Proceeding of The 13th
International Conference on Information Integration and Web-based
Applications & Services, , pp. 82 - 89,
http://dx.doi.org/10.1145/2095536.2095552

Powered by T2R2 (Science Tokyo Research Repository)Relationship Extraction Methods Based on Co-occurrencein Web Pages and Files
Qiang SONG∗

Tokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku
Tokyo, Japan†‡

Yousuke WATANABE

Haruo YOKOTATokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku
Tokyo, JapanTokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku
Tokyo, Japansoukyou@de.cs.titech.ac.jp watanabe@de.cs.titech.ac.jp yokota@cs.titech.ac.jp
ABSTRACT

Keywords

Every day, information on the Web becomes increasinglyenriched. Web access is now very useful in many aspects ofdaily life, particularly for writing documents and programs.
In fact, it has become quite usual to edit ﬁles while referringto information on the Web. During the ﬁle-editing process,we usually visit so many Web pages that we cannot remember all of the relevant ones. Later, if we want to revisit thesame Web pages to modify some part of a ﬁle, it can be very
hard to track down the Web pages originally referred to.
In this paper, we propose methods for ﬁnding relationships
between ﬁles and Web pages based on the co-occurrence ofdata in Web-access logs and ﬁle-access logs. These relationships are very useful for revisiting Web pages related totarget ﬁles. To analyze co-occurrence in these two types ofaccess logs, there are two approaches for merging the logs,
involving a trade-oﬀ between accuracy and execution time.
We call them the Pre-Merge and Post-Merge methods, andwe have evaluated these two methods using actual accesslogs.

ﬁle searching, Web page, relationship between Web pages
and ﬁles, co-occurrence frequency

Categories and Subject Descriptors
E.5 [Files]: Sorting/searching; H.3.5 [Information Storage and Retrieval]: Online Information Services—Webbased services; H.2.8 [Information Systems]: Database
ManagementDatabase Application[Data Mining]

General Terms
Experimentation∗Department of Computer Science, Graduate School of Information Science and Engineering†Global Scientiﬁc Information and Computing Center.
‡Department of Computer Science, Graduate School of Information Science and Engineering

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
iiWAS2011, 5-7 December, 2011, Ho Chi Minh City, Vietnam..
Copyright 2011 ACM 978-1-4503-0784-0/11/12 ...$10.00.

1.

INTRODUCTION

The Internet is suﬃciently established that informationon the Web is signiﬁcantly enriched every day. This meansthat the information on Web pages has become increasingly
useful in daily life. It has therefore become very common
for us to refer to information on the Web, particularly whenwriting documents or programs.
For example, suppose that a user has edited a program
ﬁle while referring to Web pages describing the programlanguage speciﬁcations or the algorithm description, and theuser tries later to modify the program during debugging. It
can be very hard to ﬁnd not only the Web pages but also
the program ﬁles themselves, because there may be manyﬁles as well as many Web pages.
Traditional desktop search engines [8, 5, 6] and Web searchengines are useful for ﬁnding an individual ﬁle or groupof Web pages if the user can remember some related keywords. However, if the user cannot recall appropriate keywords, it will be rather diﬃcult to ﬁnd the ﬁle or the Web
pages. For ﬁles that include only programs, experimental
data, and ﬁgures, for example, it becomes even more diﬃcult, because these ﬁles have no text corresponding to the
keywords. Moreover, current desktop search engines andWeb search engines cannot provide information about any
relationships between the ﬁle and the Web pages.
We have previously proposed methods to search for ﬁlescontaining no keywords [17, 13, 14, 15, 19] by analyzing ﬁleaccess logs, based on the concept that related ﬁles are frequently accessed at the same time. We have also evaluatedthe eﬀectiveness of these methods. However, although they
can search for ﬁles, they cannot extract information about
any relationships between ﬁles and Web pages. Therefore,
we cannot apply these methods directly to the scenario described above.
In this paper, we propose new methods for extracting relationships between groups of ﬁles and Web pages, both ofwhich involve the work of the same user. The proposed
methods output URLs for ﬁles and Web pages that co-occur
in the ﬁle logs and Web-access logs, in the form of a virtual folder. This means that the virtual folder will contains
URLs for ﬁles and Web pages that are related to the same“task”. Here, the term “task” stands for a work unit witha unifying context. For example, the task “writing thesis”

might refer to the image ﬁles, table ﬁles, and LaTeX ﬁlesthat were created while writing a thesis, together with someWeb pages viewed when identifying related publications.
To analyze co-occurrence in the two types of access logs,
ﬁle access and Web access, there are two approaches to merging the logs. One method merges them ﬁrst, whereas theother analyzes each log separately and ﬁnds matches between them. We name them the Pre-Merge and PostMerge methods, respectively. There is a trade-oﬀ between
them involving accuracy and execution time. We have implemented the two methods and compared their performanceusing actual access logs.
The remainder of this paper is organized as follows. In
Section 2, we explain how the two proposed methods, PreMerge and Post-Merge, work. In Section 3, we compare
these methods by reporting on experiments using actual access logs. Related work is presented in Section 4. Section 5contains conclusions and proposals for future work.

2. PROPOSED METHODS
We ﬁrst outline our goal and approach, and then describe
the logs used in this approach. We then propose two methods, Pre-Merge and Post-Merge, for extracting information
about the relevant groups of ﬁles and Web pages from thelogs.

2.1 Goal and Approach
Our goal is to search for correlated ﬁles and Web pages belonging to the same task. When a user edits speciﬁc ﬁles andvisits speciﬁc Web pages more frequently during this task,
the relationship between these ﬁles and Web pages is considered signiﬁcant. Based on this assumption, we propose touse ﬁle-access logs and Web-page-access logs to analyze therelationship between the ﬁles and Web pages referred to.
We have previously proposed methods for using ﬁle-accesslogs to analyze relationships between ﬁles to search for related ﬁles in the absence of keywords [17, 14, 13, 15, 19]. We
analyzed the timing overlaps between ﬁle accesses from theﬁle-access logs, and combined this with a full-text searchengine [17]. We then proposed a method for preparing avirtual folder containing related ﬁle data [14]. We also applied a data-mining method based on frequent-item sets [9]to identify combinations of ﬁles that appear frequently inthe ﬁle-access logs [13], combined with an overlap method[15] and ﬁle-operation (rename, move, and copy) logs [19].
However, these methods cannot treat combinations of ﬁlesand Web pages.
To extract the relationships between ﬁles and Web pages,
we need to handle two types of logs, namely ﬁle-access logs
and Web-access logs. The ﬁle-access logs can be derived
either from a ﬁle server or by using dedicated tools. There
are two types of Web-access logs, namely browser logs andproxy logs. The pros and cons of these logs will be discussed
in the next section.
In this paper, we propose two methods for utilizing thecontents of the ﬁle-access logs and Web-access logs. The
approaches of these two methods are as follows.
• Pre-Merge method: ﬁrst integrate the ﬁle-access logs
and Web-access logs using timestamp information, andthen extract frequent-item sets from the integrated
logs.
• Post-Merge method: ﬁrst apply frequent-item set ex-

traction to each of the individual logs and then associate both frequent-item sets based on the timestamp
information.
As an internal process in both methods, we adopt the FI
method (Frequent Itemsets discovery from ﬁle-access logs)
proposed in [13], where access logs are converted into transactions based on a speciﬁed duration, and frequent-item setsare extracted from the transactions. The details of thesemethods will be explained in Sections 2.3 and 2.4, respectively.

2.2

Access Logs

Two types of access logs are used in the proposed methods,
namely ﬁle-access logs containing the reading and writing
history of ﬁles, and Web-access logs that record the Webpage viewing history.

2.2.1

File-access Logs

The history of ﬁle accesses is recorded in an access-log ﬁlein the ﬁle server. Some ﬁle servers, such as Samba, havea built-in function for maintaining the ﬁle-access log thatcan be used in this approach [17]. In this paper, we use
a tool called FaccLog [3] that operates on a ﬁle server tomaintain more detailed logs, particularly for experimental
evaluations. The information written in the log comprises
the user’s connection time, action, user name, server IP,
client IP, and ﬁle path.

2.2.2

Web-access Logs

Web-access logs can be obtained in two ways. We can obtain them from HTTP proxy servers (squid [7]), or they canbe obtained directly from a user’s browser, such as Firefox[4], by using add-ons such as Boomtango [1]. The diﬀerences
between the two types of logs are as follows.
Advantage of proxy logs
• It is easy to collect Web-access logs without considering the diﬀerent types of browsers, by simply recording
all activities of all machines inside the target local area
network that use the proxy.
Disadvantages of proxy logs
• There are many irrelevant records within the logs. For
example, when a user loads a single page, all imageﬁles inside the page are recorded separately. Proxylogs therefore tend to be much larger than browser
logs.
• Because a browser has a cache to improve the responsetime for frequently visited Web pages, multiple accesses to the same Web page over a short duration
are not retained in the proxy logs. This reduces theaccuracy of the logs.
Advantage of browser logs
• This records Web pages that are visited directly via
user actions, and the log ﬁles are relatively small.
Disadvantages of browser logs
• To collect Web-access logs, we need to visit all target
client machines.

• The log-recording mechanisms of diﬀerent browsers vary.
For example, only the most recent access to a Web pageis saved in the log ﬁle in Chrome [2], while Firefox [4]records all accesses for each page.
We compared the eﬀects of using proxy and browser logs
by experiment, as reported below.

2.2.3 Log Filtering
Because a log ﬁle may contain many irrelevant records, wedevelop separate ﬁlters for ﬁle-access logs and Web-accesslogs to remove unnecessary information.
For ﬁle-access logs, we prepare in advance a list of ﬁleextensions that indicate ﬁle types, to ﬁlter out unnecessaryﬁle accesses such as accesses to system ﬁles. The logs also
contain many records of accesses to folders. Because theseaccesses are not used in our current approach, we also remove them. (We may use them in future work.) If there aremany ﬁle accesses within a very short duration (several per
second), these accesses can be considered automatic accesses
generated by software, because a human user could not access so many ﬁles so quickly. Therefore, if more than N
records are accessed in a second (in our experiments, N wasfour), we remove them from the log ﬁle. In this way, many
irrelevant access-log entries, such as ﬁle scans by antivirus
software, can be removed.
On the other hand, for the Web-access logs, we have toconsider the behavior of users. It is usual to traverse several
Web pages by clicking links to reach a useful Web page, evenwhen using a Web search engine. The viewing duration forthese stopover Web pages tends to be short until the target Web page is reached. Therefore, if a user moves quickly
to another Web page (within three seconds in our experiments), we treat the Web page as a stopover, and remove
the reference from the logs.
We also remove logs of visits to speciﬁc Web sites. For
example, users tend to access a Web mailbox such as Gmail
frequently, independently of the current task. These typesof Web access are irrelevant to ﬁnding relationships withﬁle accesses. We therefore exclude these logs using a site
exclusion list. In this list, we also exclude logs of social networking service sites such as Twitter and Facebook because
the accesses on these sites hardly have any relationship withthe current task at the most time.
In proxy logs, accesses to images within a Web page arealso recorded. Since these ﬁles, used to construct parts of a
Web page, are not a target in this approach and can be foundby the URL of Web page later, we remove logs accessingthese image ﬁles based on their ﬁle extensions: .jpg/.JPG/,.png/.PNG/, or .jpeg/.JPEG.
We delete logs for HTTP response status codes other than200, which is the standard response for successful HTTP
requests.

2.3 Pre-Merge Method
In the Pre-Merge method, we ﬁrst merge the ﬁle-accesslogs and Web-access logs, and then extract frequent-item
sets from the integrated log. Its process ﬂow is shown on
the left side of Figure 1. We describe each step below. Log
ﬁltering is performed by the procedure described in Section
2.2.3.

2.3.1 Log Merging

Figure 1: Processing Flow for Pre-Merge (Left) and
Post-Merge (Right)

Figure 2: Extracting the Overlap between Two Log
Files
We ﬁrst unify the formats of the two types of log ﬁles toenable them to be merged, then use the timestamp information to sort them in time order.

2.3.2

Overlap Extraction

It is of course very common for users to browse Web pages
independently of editing a ﬁle. Because the goal of thisresearch is to extract the relationship between ﬁles and Web
pages, we extract the overlapped part of the two logs interms of access time. We remove Web-access logs outside
a particular period (30 minutes in our experiments) before
and after a ﬁle access has occurred 2.

2.3.3

Transaction Conversion

To enable application of a transaction-based algorithm formining associations between items [9], we convert the integrated access logs into a sequence of transactions containing
log records appearing within a predeﬁned period (parameterT ransactionT ime[s]).
For example, if the integrated logs contain the records“1:02:04 w.docx”, “1:05:28 www.example.com”, “1:40:39 y.txt”,
and “2:04:06 z.pptx”, and the parameter T ransactionT ime[s]is set to 3600[s], the converted transactions are transaction1= “2.docx, www.example.com, y.txt” and transaction2 =“z.pptx”.

2.3.4 Frequent-set Discovery
In this step, we discover frequently appearing sets fromtransactions by using the Apriori algorithm [9]. We extract
combinations of the same ﬁle or Web page occurring overminimum times predeﬁned by the parameter (M inSupport).
This frequent-access-set discovery eliminates accidental simultaneous-access combinations that are not in fact related.
Figure 3: Matching in Post-Merge

2.3.5 Set Maximization
The previous step tends to generate a large number ofsmall sets containing the same elements. We merge the small
sets into a maximized one. For example, if the frequentaccess-set discovery generates {a, b, c, d} and {a, b, c, e}, theﬁles or Web pages {a, b, c, d, e} are probably related to thesame task, in spite of there being no set {a, b, c, d, e} in thefrequent-access-set discovery results.
To merge similar small sets into a larger set, we use theDice coeﬃcient, deﬁned by the following expression:
2|A ∩ B|
≥ Dice threshold|A| + |B|

Here, T ranIDs(x) means the set of transaction IDs containing x.
For example, suppose that we obtain a frequent-item set{x, y, z} for ﬁles, and {a, b, c} for Web pages, as shown in
Figure 3. When the parameter value for Overlap is three
and that for T ransactionT ime is 15 minutes, and the ﬁle x
and Web page a are both accessed in the three transactiontime periods “12:00–12:15”, “12:15–12: 30”, and “12:45–13:
00” (corresponding to the box colored black in Figure 3),
these two sets are combined.

.

3.

If the Dice coeﬃcient between two item sets, A and B, isequal to or greater than a predeﬁned threshold (parameter
Dice threshold), the sets A and B are combined into a larger
set.

We performed three experiments to ﬁnd the optimal parameter values for the Pre-Merge and Post-Merge methods,
and compared these two methods in terms of accuracy andexecution time.

2.4 Post-Merge Method

3.1

In the Post-Merge method, we ﬁrst apply the Apriori algorithm [9] to the ﬁle-access log and Web-access log individually, and then merge the results of the two frequent-item
sets. The right part of Figure 1 shows the process ﬂow forthis method. Because the sets obtained by Log Filtering(2.2.3), Transaction Conversion (2.3.3), Frequent-set Discovery (2.3.4), and Set Maximization (2.3.5) are the sameas those in the Pre-Merge method, we need only explain the
Matching step in this section.

2.4.1 Matching
After the frequent-access-set discovery for each log ﬁle, we
obtain the frequent-item sets for both ﬁles and Web pages.
Because we assume that ﬁles and Web pages for the sametask are accessed during the same time period in a transaction, we combine ﬁle sets with Web-page sets based on the
degree of overlap in access times for each element.
If the number of element pairs of overlapped transactions
is greater than or equal to a predeﬁned parameter (Overlap),
we consider the two frequent-access sets to have a strong
relationship, and combine them. The matching condition
for a frequent-access set of ﬁles fp and a frequent-access setof Web pages wq is deﬁned as follows:|T ranIDs(fp ) ∩ T ranIDs(wq )| ≥ Overlap.

EXPERIMENTS

Environment

We used the following environment for the experiments:• OS: Linux CentOS 4.3• CPU: Dual Core AMD Opteron(tm) Processor 280 *4• Memory: 16 GB (4 GB *4)

3.2 Data
The ﬁle-access logs used in these experiments were derived from the ﬁle server in our research laboratory using
a tool called Facclog. For the Web-access logs, the proxylogs in the HTTP proxy server operating in our laboratory
were recorded, and the browser logs were from the Firefox
browsers installed on each client. We used the access logs of
two distinctive users in these experiments. The details areshown in Table 1.
We prepared three datasets, which were various combinations of the users and Web-access log types, as follows:• Dataset1: File-access logs + Browser logs for User1• Dataset2: File-access logs + Proxy logs for User1• Dataset3: File-access logs + Proxy logs for User2
The reason for preparing these three datasets was that Dataset1
and Dataset2 are for the same user, the diﬀerence being thatthey combine the same ﬁle-access logs with diﬀerent types

3.4

Table 1: Data
User

Term

Log

Size (byte)

User1

2010/09/24 2010/11/21

User2

2010/10/1 2010/10/31

FileBrowser
Proxy
File
Proxy

23,624,947
2,036,315
52,332,311
42,450,684
68,546,676

Evaluation

We use P recision, Recall, and F − measure [10] to evalFile/Web page uate the results. The deﬁnitions of these metrics are:numbers|Results ∩ Examinees|472
P recision =|Results|
1731
3939
506
|Results ∩ Examinees|
Recall =3036|Examinees|
F −measure =2 ∗ P recision ∗ Recall.
P recision + Recall

(1)

(2)

(3)

We only evaluate result sets that refer to both ﬁles andWeb pages. With reference to Figure 4, we do not evaluate
Virtual Folder2 because it refers to no ﬁles. If the items ofthe correct answer set are distributed across more than one
result set, we compare each result set with the answer set
and choose the one with the highest value for Recall.

3.5
3.5.1

Figure 4: Examples of Virtual Foldersof Web-access logs. We aimed to identify the better typeof Web-access log by comparing results for Dataset1 andDataset2. On the other hand, Dataset2 and Dataset3 arefrom diﬀerent users using the same type of Web-access log.
We aimed to ﬁnd diﬀerences between users by comparing
the results for Dataset2 and Dataset3.
To evaluate our experimental results, we created correct
Answer Sets by hand for four tasks. The details are shownin Table 2.

3.3 Output Examples
We describe examples of the output from our proposed
methods in this section. As illustrated in Figure 4, we use
virtual folders to show the results. Here, a virtual folder
corresponds to a task. Two virtual folders are depicted in
Figure 4.
Virtual Folder1 contains two Perl ﬁles and four Web-page
URLs belonging to an implementation task for User1. The
desktop search engines could ﬁnd the two Perl ﬁles but wereunable to present the four Web pages to the users at thesame time. Our methods were able to identify both ﬁlesand Web pages at the same time.
Virtual Folder2 contains only Web-page URLs. The reason for this kind of output is that, when a user browses
the Web, the user will occasionally touch a ﬁle. Therefore,
these records will not be deleted in the log-ﬁltering step.
However, in the frequent-set-discovery step, the records forﬁles are removed, leaving only frequently accessed recordsof Web pages. Such sets are the results of Web browsing by
a user. The purpose of this paper is the extraction of relationships between ﬁles and Web pages, but we would notuse such result sets in experiment.

Experimental Results
Experiment 1

The goal of Experiment 1 was to determine the optimal
parameter values for the two methods. We changed the parameter values individually to derive the highest F-measurevalue. The results are shown in Table 3. The order of theparameters listed in the Parameters column of the table is“TransactionTime – MinSupport – Threshold value for Dice
– Overlap (only used in Post-Merge)”.
We found that the optimal parameter values for the two
methods are diﬀerent. Between diﬀerent users, because of
diﬀerences in their behavior, the optimal parameters are also
diﬀerent.
For T ransactionT ime, too small a value will limit theopportunities for related items to combine with each other.
Conversely, too large a value will lead to results containing
irrelevant items. We found that the optimal setting was
1800[s]for the Pre-Merge method with User1, it was 3600[s]for Post-Merge with User1, it was 3600[s] for Pre-Merge with
User2, and it was 5400[s] for Post-Merge with User2.
For the threshold value f or Dice, we found it diﬀeredsigniﬁcantly for diﬀerent users. Except for User2’s optimal
setting being 0.7, the optimal threshold value is between 0.1
and 0.4. Setting too high a threshold value will limit set
uniﬁcation and will lead eventually to low Recall values.
For Overlap in the Post-Merge method, values of 3 or 4
are optimal in all cases. If we set a value of up to 6, thefrequent sets for ﬁles and Web pages will no longer unite,meaning that we cannot get a ﬁnal result that refers to bothﬁles and Web pages.

3.5.2

Experiment 2

In Experiment 2, we used the optimal parameter values
derived in Experiment 1 to compare the accuracy of the PreMerge and Post-Merge methods. The results are depicted
as graphs in Figure 5.
The results indicate that Pre-Merge performs signiﬁcantly
better than Post-Merge on all Precision, Recall, and F-measure
metrics. We consider that there are two reasons for this.
Firstly, from the nature of Web pages, there are only a
few Web page sets that appear frequently. For example,
suppose that ﬁles “a, b, and c” and Web page “w” belong

User
User1

User2

Set
S1
S2
S3
S4

DatasetDataset1

Table 2: Answer Sets
Content
Extensions
Files
Implementation of the core part java, pptx
24
Implementation of the ﬁlter
pl, txt
8
Seminarpdf, pptx
2
Academic management
bmp, pdf, xlsx
14doc, docx, pptx

MethodPre-Merge

Post-Merge

Dataset2

Pre-Merge

Post-Merge

Dataset3

Pre-Merge
Post-Merge

Web page numbers
1
14
7
4

Table 3: Optimal Parameter Values
Parameter Answer set Precision Recall F-measure
1800-2-0.1
S1
0.61
0.76
0.68
S2
1.00
0.86
0.93
S3
1.00
0.67
0.80
average
0.87
0.76
0.80
3600-2-0.4-3
S1
0.56
0.76
0.64
S2
0.21
0.13
0.16
S3
0.00
0.00
0.00
average
0.26
0.30
0.27
1800-2-0.3
S1
0.00
0.00
0.00
S2
1.00
0.36
0.53
S3
0.80
0.44
0.57
average
0.60
0.27
0.37
3600-2-0.4-3
S1
0.56
0.76
0.64
S2
0.21
0.13
0.16
S3
0.00
0.00
0.00
average
0.26
0.29
0.27
3600-2-0.3
S1
0.80
0.22
0.35
average
0.80
0.22
0.35
5400-2-0.7-4
S1
0.10
0.17
0.13
average
0.10
0.17
0.13

to the same task, and that every time a user edits ﬁle “a”,
“b”, or “c”, page “w” is accessed. Under this assumption,
the frequent-access set {a, b, c, w} will be derived in the PreMerge method. However, for Post-Merge, the frequent sets
for ﬁles and Web pages are calculated separately, so we will
derive only {a, b, c} because no other Web pages are accessed
together with “w”. In other words, “w” will not be extracted
into any frequent set before matching, because it is a singleton with respect to Web accesses. That is, because the frequent sets for Web pages tend to be small in the Post-Merge
method, its accuracy will be worse. The same phenomenon
is occurred in the case that a ﬁle is a singleton in the uniﬁed
frequent-access set.
Secondly, in the matching step of Post-Merge, it is possiblethat some unrelated items are matched into the ﬁnal result.
This also decreases the accuracy of the Post-Merge method.
It would appear to be necessary to improve the matchingprocess in future.
In addition, the period of collected logs used in these experiments was about 1–2 months. When we apply the two
methods to longer periods of log data in the future, we would
expect that the accuracy diﬀerences will be larger.
Comparing the results for Dataset1 and Dataset2, the useof browser logs performs better than the use of proxy logs on
all Precision, Recall, and F-measure metrics. We consider
that there are also two reasons for this.
Firstly, the proxy logs contain too many irrelevant logs

Total numbers
25
22
9
18

Execution time[s]

35.31

18.85

38.79

22.81
67.38
24.38

such as records of advertising sites and loading records formaterial embedded in a Web page. These decrease the Precision values for the proxy logs directly.
Secondly, because of the cache function in browsers, thebrowser will not load the same Web page from Web servers
again until the cache expires. Therefore, the access history
for the same Web pages within a short period may be foundin the browser logs, but not in the proxy logs. This decreases
the Recall values for the proxy logs.

3.5.3

Experiment 3

Experiment 3 uses the optimal parameter values from Experiment 1 to compare the two methods in terms of execution time. The results are shown in Figure 6.
For Dataset1, the Pre-Merge method takes 1.87 times
longer than the Post-Merge method. This is 1.70 times
longer for Dataset2, and even reaches 2.76 for Dataset3. We
consider that there are two reasons for this.
Firstly, the frequent-access-set discovery step is the mosttime-consuming step for both methods, and its execution
time depends on the size of the logs. Because Pre-Merge
merges both logs ﬁrst, the size of the logs becomes larger
before calculating the frequent sets.
Secondly, when Pre-Merge combines the two logs, it isnecessary to sort the two logs in order of timestamps. Thisis also time consuming.
We should expect that, when we apply the proposed methods to larger log datasets in future, the diﬀerences in exe-

Figure 6: Comparison of the Two Methods in Termsof Execution Time

Figure 5: Comparison of the Two Methods in Termsof Accuracy

cution time will be even larger. Therefore, improving theprocessing eﬃciency in Pre-Merge is a big problem to besolved.

4. RELATED WORK
There are some popular desktop search engines, such as
Windows Search [8], Google Desktop [5], and Spotlight [6] in
Mac OS X. However, because these desktop search engines
all use textual information inside ﬁles for keyword searching, there is the problem that they cannot ﬁnd nontextbased ﬁles such as image and video ﬁles. Another problem
is that they all require the user to input appropriate keywords, whereas ﬁles associated with the same piece of work
do not always use the same keywords. For this reason, using traditional desktop search engines to search for all ﬁlesbelonging to a task without missing some of them is very
diﬃcult, particularly when the scale of the task is large.
FRIDAL [17, 18] is a system for solving the problem ofdesktop search engines ﬁnding ﬁles containing no textual information. FRIDAL calculates the relationship between ﬁlesusing information such as overlap counts, overlap durations,and diﬀerences in open times in the ﬁle-access logs. It thenutilizes the relationships to provide related ﬁles to add to theresults of a traditional desktop search engine. Therefore, it
is capable of providing related ﬁles that do not contain thegiven keyword directly.
The approach of FRIDAL is expanded in the Clustering using Overlap of ﬁle-use (CO) method [14], the FI [13]method, and the COFI [15] method. The goal of each ofthese three methods is to list ﬁles associated with the sametask in a virtual folder, even though the ﬁles may be distributed across multiple directories in the ﬁle system. In
other words, the goal of these methods is to group ﬁles bytask.
The CO method discovers ﬁles whose times of use overlap.
It then uses hierarchical clustering to group the ﬁles into
virtual folders. The CO method can ﬁnd ﬁles distributed
across the ﬁle system. However, the problem is that evenﬁles belonging to the same task may not overlap. Thus, COcannot ﬁnd ﬁles whose access times do not overlap.
The FI method is an improved version of the CO method.
It converts ﬁle accesses into a sequence of transactions deﬁned over a certain period, and then ﬁnds the frequently
appearing combinations of ﬁles. It also outputs its results
into virtual folders.
The COFI method is a method based on both the CO andFI methods. It ﬁrst derives the relationships between ﬁle accesses from ﬁle-access logs using the concept of a transaction.
It then calculates the relationships between the transactions
using overlap information, similarly to the CO method.
Based on an assumption that a set of Rename, Move, andCopy (RMC) operations tends to initiate a new task, the
SUGOI [19] system detects two types of tasks, FI tasks and
RMC tasks, from ﬁle-access logs. An FI task corresponds toa group of ﬁles frequently accessed together; an RMC task isgenerated by RMC operations and then constructs a graphof intertask relationships based on the inﬂuence of RMC
operations and the similarity between tasks. Experiments
using actual ﬁle-access logs indicate that the SUGOI systemsigniﬁcantly improves search results of the COFI methods.
Connections [16] is a ﬁle search system that uses contextual information with the aim of enhancing full-text search
results. Connections generates a relational graph of ﬁlesbased 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 fulltext search engine.
Semantic Desktop Search [11] extracts the attributes fromeach ﬁle, then search ﬁles using the attributes. However, it isnecessary to write programs for each type of ﬁles to extract
the attributes. Our methods are independent of ﬁle formats.
Because the targets of these above-mentioned methods are
ﬁle accesses only, with no consideration of Web access, themain contribution of this paper is the combined treatment
of ﬁle-access logs and Web-access logs to derive relationships
between them.
OreDesk [12] is a tool that can search both ﬁles and Web
pages browsed in the past, as a type of time machine. OreDesk records the behavior of speciﬁc applications by installing plug-ins in them. OreDesk then shows its results ona timeline. For example, by reviewing a previous timeline,
users can ﬁnd those Web pages that were browsed when creating a Word ﬁle. However, the problem is that, if the user
cannot remember when the Word ﬁle was created, the user
will have to check the whole timeline. A signiﬁcant diﬀerence between OreDesk and our methods is that our methods
can classify ﬁles and Web pages for a task automatically, by
calculating access frequencies.

5. CONCLUSIONS AND FUTURE WORKIn this paper, we have proposed two methods for extracting groups of ﬁles and Web pages used in the same task
into a virtual folder that provides a means of revisiting related ﬁles and Web pages. We analyzed two types of accesslogs, ﬁle-access logs and Web-access logs, deriving relationships between ﬁles and Web pages by applying a data mining
technique. We named the methods Pre-Merge and PostMerge, where the former method ﬁrst merges the two typesof logs and then ﬁnds the relationships, whereas the lattermethod ﬁrst analyzes each type of log separately and thenﬁnds matches between them.
We evaluated the two methods using actual access logs
from our laboratory. In the experiments, we ﬁrst determined optimal parameter values for each method, and thencompared their accuracy, Precision, Recall, and F-measure.
We also compared the execution times for the two methods,
using the optimal parameter values. The results of the experiments indicate that there is a trade-oﬀ between accuracy
and execution time for these methods. Pre-Merge performs
better than Post-Merge for all of the Precision, Recall, andF-measure metrics. However, Pre-Merge takes from 1.70 to
2.76 times longer than Post-Merge. For the size of log ﬁlesused in the experiments, the diﬀerence in accuracy is moresigniﬁcant than the execution times, and we conclude that
the Pre-Merge method is preferable. However, for larger log
ﬁles, the diﬀerences in execution time will increase and may
become a serious problem. We therefore plan to evaluate
the methods using longer-period logs in the future.
In future work, we also plan to reﬁne the methods to improve accuracy, to reduce execution time, to determine optimal parameter values automatically from user behavior, andto experiment with larger log ﬁles.

6.

ACKNOWLEDGMENTS

Part of this research was supported by MEXT via a Grantin-Aid for Scientiﬁc Research #22240005.

7.

REFERENCES[1] Boomtango. http://www.boomtango.com/.
[2] Chrome. http://www.google.com/chrome/.
[3] Facclog.
http://www2s.biglobe.ne.jp/~masa-nak/fal down
.htm.
[4] Firefox. http://mozilla.jp/ﬁrefox/.
[5] Google desktop. http://desktop.google.com/.
[6] Mac os x spotlight.
http://www.apple.com/server/macosx/features/spotlightserver.html.
[7] Squid cache. http://www.squid-cache.org/.
[8] Windows search.
http://www.microsoft.com/windows/products/winfamily/
desktopsearch/default.mspx.
[9] R. Agrawal, T. Imieliński, and A. Swami. Mining
association rules between sets of items in large
databases. Proc. ACM SIGMOD, pages 207–216, 1993.
[10] R. Baeza-Yates and B. Ribeiro-Neto. Modern
Information Retrieval. Addison Wesley, 1999.
[11] A. Chirita, R. Gavriloaie, S. Ghita, W. Nejdl, and
R. Paiu. Activity based metadata for semantic
desktop search. Proc. Second European Semantic Web
Conference(ESWC 2005), pages 439–454, 2005.
[12] R. Ohsawa, K. Takashio, and H. Tokuda. Oredesk: A
tool for retrieving data history based on user
operations. IEEE International Symposium on
Multimedia (ISM 2006), pages 762–765.
[13] K. Otagiri, Y. Watanabe, and H. Yokota. Access-log
analysis for virtual directory creation to restore ﬁlesused in user’s works. Information Processing Society ofJapan, 2009.
[14] K. Otagiri, Y. Watanabe, and H. Yokota. Access-log
based virtual directory creation to restore user’s
works. In DEIM Forum 2009, 2009.
[15] K. Otagiri, Y. Watanabe, and H. Yokota. Virtual
directory creation considering access-times in frequent
accessed ﬁle sets. DEIM Forum 2010, 2010.
[16] C. A. N. Soules and G. R. Ganger. Connections: using
context to enhance ﬁle search. Proc. of SOSP’05,
pages 119–132, 2005.
[17] T. Watanabe, T. Kobayashi, and H. Yokota. A method
for searching keyword-lacking ﬁles based on interﬁlerelationships. In OTM ’08: Proceedings of the OTM
Confederated International Workshops and Posters on
On the Move to Meaningful Internet Systems, pages
14–15, Berlin, Heidelberg, 2008. Springer-Verlag.
[18] T. Watanabe, T. Kobayashi, and H. Yokota. Searching
keyword-lacking ﬁles based on latent interﬁlerelationship. Software and Data Technologies, pages
236–244, 2010.7.
[19] Y. Wu, K. Otagiri, Y. Watanabe, and H. Yokota. A
ﬁle search method based on intertask relationships
derived from access frequency and rmc operations onﬁles. 22nd International Conference on Database andExpert Systems Applications (DEXA 2011), pages
364–378, 2011.